原题链接：Leetcode 419. Battleships in a Board
Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.
Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
Example 1:
Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2
Example 2:
Input: board = [["."]]
Output: 0
Constraints:
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] is either
'.'or'X'.
Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the values board?
题目大意：
有一个m x n 的矩阵代表着甲板，甲板中有着若干的战舰。
战舰只能水平或者竖直放置。
一艘战舰在矩阵中用长度为1，宽度为k的字符 'X'组成的块来表示。战舰之间不彼此相连，问你甲板中战舰的数量。
方法二：枚举起点
思路：
由于战舰总是水平或竖直放置，我们可以认定水平战舰的最左端和竖直战舰的最上端为战舰的起点。
遍历一遍二维数组，只需要统计起点的个数就能得道战舰的数量。
这也正是补充中提到的不改变矩阵的方法。
C++ 代码:
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
// 加班的行数和列数
int row = board.size();
int col = board[0].size();
int ans = 0;
for(int i = 0; i < row; i++ ){
for(int j = 0; j < col; j++ ){
if(board[i][j] == 'X'){
if(i > 0 && board[i - 1][j] == 'X')
continue;
if(j > 0 && board[i][j - 1] == 'X')
continue;
ans++;
}
}
}
return ans;
}
};
复杂度分析：
- 时间复杂度：O(mn)，遍历了一遍二维数组
- 空间复杂度：O(1)
