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;
}
};
c++ dfs solution very easy to understand


Thanks for your solution.
But I think your code lack the test for invalid board such as :
X...
XXXX
X...
So I add this lineif (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); }