BFS_C++_Accepted_3ms


  • 0
    class Solution {
    public:
    int countBattleships(vector<vector<char>>& board) {
        if(board.empty()) return 0;
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> check(m, vector<bool>(n, false));
        int res = 0;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(board[i][j] == 'X' && check[i][j] == false){find(board, check, res, i, j, m, n);}
            }
        }
        return res;
    }
    
    void find(vector<vector<char>>& board, vector<vector<bool>>& check, int& res, int i, int j, int m, int n){
        check[i][j] = true;
        int k = 0;
        if(i < m - 1 && board[i + 1][j] == 'X' && check[i + 1][j] == false){find(board, check, res, i + 1, j, m, n); k = 1;}
        if(i > 0 && board[i - 1][j] == 'X' && check[i - 1][j] == false){find(board, check, res, i - 1, j, m, n); k = 1;}
        if( j < n - 1 && board[i][j + 1] == 'X' && check[i][j + 1] == false){find(board, check, res, i, j + 1, m, n);k = 1;}
        if( j > 0 && board[i][j - 1] == 'X' && check[i][j - 1] == false){find(board, check, res, i, j - 1, m, n);k = 1;}
        if(k == 0) ++res;
    }
    };
    

    0_1476821454339_F84C28A2-606E-415D-AF7F-B15BF797E45E.png


Log in to reply
 

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