O(mn) time O(1) space
对于每个X只要确定左边和上边不是X就行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
if (board.empty() || board[0].empty()) return 0;
int res = 0;
int n = board.size(), m = board[0].size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if ((board[i][j] == 'X')
&& (i == 0 || board[i - 1][j] != 'X')
&& (j == 0 || board[i][j - 1] != 'X')) {
++res;
}
}
}
return res;
}
};
|