419. Battleships in a Board - cocoder39/coco39_LC GitHub Wiki

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int res = 0;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (! visited[i][j] && board[i][j] == 'X') {
                    res++;
                    dfs(board, visited, i, j);
                }
            }
        }
        return res;
    }
private:
    void dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, int row, int col) {
        visited[row][col] = true;
        
        int m = board.size(), n = board[0].size();
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto dir : dirs) {
            int r = row + dir.first, c = col + dir.second;
            if (r >= 0 && r < m && c >= 0 && c < n && ! visited[r][c] && board[r][c] == 'X') {
                dfs(board, visited, r, c);
            }
        }
    }
};