LeetCode 题解工作台
棋盘上的战舰
给你一个大小为 m x n 的矩阵 board 表示棋盘，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在棋盘 board 上放置的 舰队 的数量。 舰队 只能水平或者垂直放置在 board 上。换句话说，舰队只能按 1 x k （ 1 行， k 列）或 k x 1 （ k …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以遍历矩阵，找到每个战舰的左上角，即当前位置为 `X` 且上方和左方都不是 `X` 的位置，将答案加一。 遍历结束后，返回答案即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 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.lengthn == board[i].length1 <= m, n <= 200board[i][j]是'.'或'X'
进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？
解题思路
方法一：直接遍历
我们可以遍历矩阵，找到每个战舰的左上角，即当前位置为 X 且上方和左方都不是 X 的位置，将答案加一。
遍历结束后，返回答案即可。
时间复杂度 ，其中 和 分别是矩阵的行数和列数。空间复杂度 。
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m, n = len(board), len(board[0])
ans = 0
for i in range(m):
for j in range(n):
if board[i][j] == '.':
continue
if i > 0 and board[i - 1][j] == 'X':
continue
if j > 0 and board[i][j - 1] == 'X':
continue
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) because each cell is visited once during scanning and DFS. Space complexity can be O(1) if modifying the board in place, or O(m_ n) for a separate visited matrix. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for efficient in-place traversal without extra memory.
- question_mark
Expect handling of edge cases like single-row or single-column boards.
- question_mark
Clarify that ships never touch diagonally or directly adjacent.
常见陷阱
外企场景- error
Counting the same battleship multiple times by not checking previous cells.
- error
Ignoring the separation rule and merging distinct ships.
- error
Recursion stack overflow on very large boards without proper base cases.
进阶变体
外企场景- arrow_right_alt
Boards with wrap-around edges where ships can connect across boundaries.
- arrow_right_alt
Counting ships that can touch diagonally but not orthogonally.
- arrow_right_alt
Return the coordinates of each battleship instead of just the count.