The follow-up question is fun: "Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?"
When we meet an 'X', we need to check if it is vertical or horizontal: they will never happen at the same time, by problem statement. For horizontal, we simply stripe through right, and plus 1 - however, if our top element is 'X' already, it is a vertical and counter has alread been increased.
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int h = board.size();
if (!h) return ;
int w = board[].size();
if (!w) return ;
int cnt = ;
for(int i = ; i < h; i ++)
for(int j = ; j < w; j ++)
{
if(board[i][j] == 'X')
{
// is it a counted vertical case?
if(!(i > && board[i -][j] == 'X'))
{
cnt ++;
// Horizontal
while(j < (w - ) && board[i][j + ] == 'X') j ++;
}
}
}
return cnt;
}
};