419. 棋盘上的战舰

🟠   🔖  深度优先搜索 数组 矩阵  🔗 力扣 LeetCode

题目

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 的矩阵 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. 观察战舰的特征

   • 在 m x n 的棋盘上：
     • 'X' 代表战舰的一部分，. 代表水域。
     • 战舰只能是水平或垂直排列的连续 'X'。
     • 战舰不会相邻，即不会形成 L 形。
   • 目标是统计战舰的数量。

2. 只统计战舰的起点

   • 直接遍历棋盘，只在战舰的“起点”进行计数，避免重复计算：
   • 如果当前格子是 'X'：
     • 且左边是水域（j == 0 || board[i][j-1] == '.'）。
     • 且上方是水域（i == 0 || board[i-1][j] == '.'）。
     • 那么它就是一个新战舰的起点。
   • 这样，每艘战舰只会被计数一次。

3. 初始化

   • 获取棋盘的行数 m 和列数 n。
   • 定义 battleships 变量，初始值为 0。

4. 遍历棋盘

   • 外层循环遍历所有行 i。
   • 内层循环遍历所有列 j。
   • 如果当前位置是 'X'，并且满足 左边和上方都不是 'X'，说明发现了一艘新的战舰，battleships++。

5. 返回 battleships 作为最终答案。

复杂度分析

• 时间复杂度：O(m * n)，遍历整个矩阵一次。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function (board) {
	const m = board.length;
	const n = board[0].length;
	let battleships = 0;

	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (board[i][j] === 'X') {
				// 只在战舰头部（左侧和上侧没有X）进行计数
				const left = i === 0 || board[i - 1][j] === '.';
				const upper = j === 0 || board[i][j - 1] === '.';
				if (left && upper) {
					battleships++;
				}
			}
		}
	}
	return battleships;
};

相关题目

题号	标题	题解	标签	难度	力扣
200	岛屿数量	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
286	墙与门 🔒		广度优先搜索 数组 矩阵	🟠	🀄️ 🔗
695	岛屿的最大面积	[✓]	深度优先搜索 广度优先搜索 并查集 2+	🟠	🀄️ 🔗
994	腐烂的橘子	[✓]	广度优先搜索 数组 矩阵	🟠	🀄️ 🔗