目标
给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。
战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。
示例 1：
输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2示例 2：
输入：board = [["."]]
输出：0说明：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
board[i][j]是 '.' 或 'X'
进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？
思路
这道题的描述很容易让人误解成只允许在'X'的位置上建造战舰，并且满足规则战舰不能相邻，问最多能造多少战舰。
但实际上题目的含义是，有一个棋盘，棋盘上放着战舰，每个战舰由k个'X'表示，战舰的形状是 1*k 或者 k*1，战舰的排放规则是不能相邻，让我们统计战舰数量。
刚开始想到的是使用一个二维数组保存是否访问过，从第一行开始从左到右访问，如果为'X'则向下延伸并将visited置为true。
后来看了题解，可以将原数组的'X'置为其它标记，这样就不用额外的空间了。
进阶的问题是不修改board，根据排列规则，仅统计战舰的起点，即上面与左边不能为'X'。
也有网友使用dfs来处理，子节点是下方与右侧的元素，如果是'X'则改为其它标记，否则返回。其实直接循环遍历更方便一些。
还有网友使用并查集计算连通分量，其实也没有必要。并查集主要用于快速判断元素是否属于同一个集合，统计集合中元素个数，集合元素的合并。这里仅需要连通分量个数，并且连通的关系很简单，纵向或横向，并不像图遍历那样复杂，直接计数即可。
代码
/**
* @date 2024-06-11 8:40
*/
public class CountBattleships419 {
/**
* 网友题解
* 一次扫描，不使用额外空间，不修改board
* 统计左上顶点
* 需满足条件：顶点左侧与上侧不能为'X'
*/
public int countBattleships_v2(char[][] board) {
int ans = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == 'X' &&
(j == 0 || board[i][j - 1] != 'X') &&
(i == 0 || board[i - 1][j] != 'X')) {
ans++;
}
}
}
return ans;
}
/**
* 看了题解，可以直接将board中的'X'置为'.'，这样就不需要额外的visited数组了
* 一次扫描，但是修改了board
*/
public int countBattleships_v1(char[][] board) {
int res = 0;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
int j = 0;
while (j < n) {
if (board[i][j] == 'X') {
res++;
int k = i + 1;
while (k < m && board[k][j] == 'X') {
board[k][j] = '.';
k++;
}
while (j < n && board[i][j] == 'X') {
board[i][j] = '.';
j++;
}
} else {
j++;
}
}
}
return res;
}
/**
* 一次扫描，但是使用了额外的空间
*/
public int countBattleships(char[][] board) {
int res = 0;
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
int j = 0;
while (j < n) {
if (visited[i][j]) {
j++;
continue;
}
if (board[i][j] == 'X') {
res++;
int k = i;
while (k < m && board[k][j] == 'X') {
visited[k][j] = true;
k++;
}
while (j < n && board[i][j] == 'X') {
visited[i][j] = true;
j++;
}
} else {
j++;
}
}
}
return res;
}
}
性能
使用额外空间
不使用额外空间
