---

0419. 棋盘上的战舰

• 标签：深度优先搜索、数组、矩阵
• 难度：中等

题目链接

• 0419. 棋盘上的战舰 - 力扣

题目大意

描述：

给定一个大小为 $m \times n$ 的矩阵 $board$ 表示棋盘，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.'。

「舰队」只能水平或者垂直放置在 $board$ 上。换句话说，舰队只能按 $1 \times k$（$1$ 行，$k$ 列）或 $k \times 1$（$k$ 行，$1$ 列）的形状放置，其中 $k$ 可以是任意大小。两个舰队之间至少有一个水平或垂直的空格分隔 （即没有相邻的舰队）。

要求：

返回在棋盘 $board$ 上放置的「舰队」的数量。

说明：

• $m == board.length$。

• $n == board[i].length$。

• $1 \le m, n \le 200$。

• $board[i][j]$ 是 '.' 或 'X'。

• 进阶：你可以实现一次扫描算法，并只使用 $O(1)$ 额外空间，并且不修改 $board$ 的值来解决这个问题吗？

示例：

• 示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

• 示例 2：

输入：board = [["."]]
输出：0

解题思路

思路 1：一次扫描 + 左上角检测

1. 由于战舰只能水平或垂直放置，且战舰之间不相邻，我们可以通过检测战舰的"头部"来统计战舰数量。
2. 战舰的"头部"是指战舰最左上角的 'X' 位置。对于水平战舰，头部是同一行中最左边的 'X'；对于垂直战舰，头部是同一列中最上面的 'X'。
3. 我们可以通过一次扫描整个棋盘，对于每个 'X' 位置 $(i, j)$，检查其左边 $(i, j-1)$ 和上边 $(i-1, j)$ 是否也是 'X'。
4. 如果左边或上边是 'X'，说明当前位置不是战舰头部，跳过；否则，当前位置是战舰头部，计数器加 $1$。
5. 这样我们只需要一次扫描就能统计出所有战舰的数量，时间复杂度为 $O(m \times n)$，空间复杂度为 $O(1)$。

思路 1：代码

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m, n = len(board), len(board[0])
        count = 0
        
        # 遍历整个棋盘
        for i in range(m):
            for j in range(n):
                # 如果当前位置是 'X'
                if board[i][j] == 'X':
                    # 检查是否为战舰头部
                    # 战舰头部：左边和上边都不是 'X'（或者超出边界）
                    is_head = True
                    
                    # 检查左边
                    if j > 0 and board[i][j-1] == 'X':
                        is_head = False
                    
                    # 检查上边
                    if i > 0 and board[i-1][j] == 'X':
                        is_head = False
                    
                    # 如果是战舰头部，计数器加 1
                    if is_head:
                        count += 1
        
        return count

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$，其中 $m$ 是棋盘的行数，$n$ 是棋盘的列数。需要遍历整个棋盘一次。
• 空间复杂度：$O(1)$，只使用了常数额外空间，没有使用额外的数据结构。