🔗 🟡 419. Battleships in a Board

tags: `矩陣(Matrix)` `DFS`

題意

注意單數和複數的區別，單數是指一艘戰艦，這裡把複數的戰艦稱為「艦隊」。

給定一個 $m \times n$ 的矩陣 $board$ ，其中每個單元格是一艘戰艦 'X' 或空的 '.'，返回板上「艦隊」的數量。

「艦隊」只能沿著水平或垂直方向，即它們只能是 $1 \times k$ （ $1$ 行， $k$ 列）或 $k \times 1$ （ $k$ 行， $1$ 列）的形狀， $k$ 可以是任何大小。兩個艦隊之間至少有一個水平或垂直的單元格分隔（即沒有相鄰的艦隊）。

後續問題：你能夠用一次遍歷，只使用 $O(1)$ 的額外記憶體，且不修改 $board$ 的值來完成嗎？

思路：只計算起點

這個問題其實與 200. Number of Islands 很類似，只是在該題中我們可以往四個方向進行 DFS，而在這個問題中，我們只能往右和往下進行 DFS。但在使用 DFS 的過程中，需要使用額外的陣列 $visited$ 來記錄已經訪問過的單元格，或是直接修改 $board$ 的值，這樣就不符合題目的要求了。

不過我們可以注意到，根據題意，艦隊只能沿著水平或垂直方向，故若一個艦隊的左上角是 $(x, y)$ ，可以將其視為這個艦隊的起點，且一定滿足以下兩個條件：

若 $x > 0$ ，則 $(x-1, y)$ 一定是 '.'；
若 $y > 0$ ，則 $(x, y-1)$ 一定是 '.'。

這樣我們就可以只計算起點，而不用進行 DFS。

枚舉所有的點，若該點是 'X' 且滿足上述兩個條件，則這個點一定是一個艦隊的起點，計算起點的數量即可。

複雜度分析

時間複雜度： $O(m \cdot n)$ ，需要遍歷所有的點。
空間複雜度： $O(1)$ 。

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        ans = 0
        for i, row in enumerate(board):
            for j, x in enumerate(row):
                if x == '.':
                    continue
                if (i == 0 or board[i-1][j] == '.') and (j == 0 or board[i][j-1] == '.') :
                    ans += 1
        return ans

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.'))
                    ans++;
        }
        return ans;
    }
};