c++ dfs solution very easy to understand


  • 1
    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;
        }
    };
    

  • 0
    A

    Thanks for your solution.
    But I think your code lack the test for invalid board such as :
    X...
    XXXX
    X...
    So I add this line

    if (row + 1 < board.size() && board[row + 1][col] == 'X')
            {
                /* invalid board will be tested here */
                if (col + 1 < board[0].size() && board[row][col + 1] == 'X')  
                {
                    cerr << "invalid board" << endl;
                    exit(-1);
                }
                else
                    dfs(board, visited, row + 1, col);
            }
    

Log in to reply
 

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