c++ dfs solution very easy to understand


  • 0
    Q
    class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int res = 0;
            int len1 = board.size();
            if(len1 == 0)
                return 0;
            int len2 = board[0].size();
            vector<vector<bool>> visited(len1, vector<bool>(len2,false));
            for(int i=0;i<len1;i++){
                for(int j=0;j<len2;j++){
                    if(!visited[i][j] && board[i][j] == 'X'){
                        dfs(board, visited, i, j);
                        res += 1;
                    }
                }
            }
            return res;
        }
        
        void dfs(vector<vector<char>>& board, vector<vector<bool>> &visited, int i, int j){
            if(visited[i][j] == true)
                return;
            visited[i][j] = true;
            if(board[i][j] == '.')
                return;
            else{
                if(i+1 < board.size() && board[i+1][j] == 'X')
                    dfs(board, visited, i+1, j);
                if(j+1 < board[0].size() && board[i][j+1] == 'X')
                    dfs(board, visited, i, j+1);
            }
            return;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.