友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
419. 棋盘上的战舰
给你一个大小为 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 的值来解决这个问题吗？
思路分析
对矩阵全扫描，遇到战舰就+1，如果当前节点的上一个节点或者坐标一个节点是 X，已经计数过了，就跳过。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-08-07 22:40:32
*/
public int countBattleships(char[][] board) {
int m = board.length, n = board[0].length;
int result = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (board[r][c] == 'X') {
if (r > 0 && board[r - 1][c] == 'X') {
continue;
}
if (c > 0 && board[r][c - 1] == 'X') {
continue;
}
result++;
}
}
}
return result;
}
// public int countBattleships(char[][] board) {
// int m = board.length, n = board[0].length;
// int result = 0;
// // TODO 还需要处理一行一列的情况
// for (int i = 0; i < m; i++) {
// for (int j = 0; j < n; ) {
// if (board[i][j] == 'X') {
// int next = scan(board, i, j, false);
// if (next - 1 > j || (next - 1 == j && (i + 1 < m && board[i + 1][j] == '.'))) {
// result++;
// }
// j = next;
// } else {
// j++;
// }
// }
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; ) {
// if (board[j][i] == 'X') {
// int next = scan(board, i, j, true);
// if (next - 1 > j) {
// result++;
// }
// j = next;
// } else {
// j++;
// }
// }
// }
// return result;
// }
//
// private int scan(char[][] board, int row, int col, boolean isRow) {
// if (isRow) {
// for (int i = row; i < board.length; i++) {
// if (board[i][col] != 'X') {
// return i;
// }
// }
// return board.length;
// } else {
// for (int i = col; i < board[row].length; i++) {
// if (board[row][i] != 'X') {
// return i;
// }
// }
// return board[0].length;
// }
// }