# BFS_C++_Accepted_3ms

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

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