# C++ 3ms 6 lines solution with runtime O(n) and space O(1)

• Idea is to define upper left X as the head of battle ship. We simply need to count the number of heads.

int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) { return 0; }
int m = board.size(), n = board[0].size(), cnt = 0;

for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
cnt += board[r][c] == 'X' && (r == 0 || board[r - 1][c] != 'X') && (c == 0 || board[r][c - 1] != 'X');

return cnt;
}

• Thank you for the answer! I have a question that why I write (r == 0 || board[r][c-1] != 'X') && (c == 0 || board[r-1][c] != 'X') it shows runtime error but (r == 0 || board[r-1][c] != 'X') && (c == 0 || board[r][c-1] != 'X') works fine?

• @owenxbw93
Because (r == 0 || board[r][c-1] != 'X') && (c == 0 || board[r-1][c] != 'X') can't guarantee c-1 or r-1 are always non-negative.

• @soamaaazing Thanks for your solution! I'm thinking on how to deal with situation when it is negative.
(r == 0 || board[r - 1][c] != 'X' ) This is really awesome!