题目描述
求所有战舰数量,战舰只能是一维的形状,在合法情况下,两艘战舰之间必定有空隙。
由于要求常数空间,所以不能像岛屿数量那题用BFS计算。但考虑到战舰的特殊形状,只需要考虑board[i][j]左边以及上边是否是X,若为X就不计数。
C++ 代码
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int res = 0;
for (int i = 0; i < board.size(); i ++)
for (int j = 0; j < board[0].size(); j ++)
{
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
if (board[i][j] == 'X') res ++;
}
return res;
}
};