题目描述
思路解析
一句话答案：LeetCode 419 棋盘上的战舰用一次网格扫描只数舰头：X 且上、左都不是 X 就是船头、计一次数，靠战舰互不相邻保证船头唯一。时间 O(m·n)、空间 O(1)。
棋盘上摆着 X 和空位，这道题要数出几艘船
给一个 m×n 的棋盘 board，每格要么是战舰的一段 X、要么是空位点。战舰只能横排成 1×k 或竖排成 k×1 的一条直线，且任意两艘之间至少隔一个空格、绝不挨着。返回一共有几艘战舰。题面那张棋盘的答案是 2：左上角 (0,0) 一艘单格船，最右一列 (0,3)、(1,3)、(2,3) 连成一艘竖排三格船。
把整艘船找出来再数，多花的是哪一笔
一个直觉做法是对每个还没数过的 X 做一次 DFS，顺着连通的格子一路铺开、把整艘船都标记掉，铺开几次就是几艘船。答案没错，但每铺一次都要开访问标记数组、或往递归栈里压一串格子，额外空间涨到 O(m·n)。而这题的进阶要求偏偏是只用 O(1) 额外空间、还不许改动原棋盘，染色法两条都踩线。
既然每艘船都是直线，何必把它整条走完
换个数法：不找整艘船，只找每艘船左上角那一格。横排船的最左格、竖排船的最上格就是它的「船头」，每艘船有且只有一个船头，数船头就等于数船。怎么认船头？看这个 X 的正上方和正左方：上、左都不是 X，说明前面没有同船的格子接着，它就是船头，计一次数；只要上或左有一个是 X，它就是后半截，跳过。之所以不重不漏，全靠「任意两艘至少隔一格」：船与船不相邻，一个 X 的上、左邻居只可能是同船的格子、绝不会牵到隔壁船，「上左都不是 X」就精准卡住了每艘船唯一的那个头。
一行一行扫过去，每个 X 只做一道判断题
扫描顺序是从上到下、每行从左到右。碰到空位点直接跳过；碰到 X，就做那道判断题：它上边一格（同列上一行）、左边一格（同行左一列）是不是 X。两个都不是 X，船头计数加一；只要有一个是 X，跳过。第 0 行的 X 上方是棋盘外、第 0 列的 X 左方是棋盘外，都视作那侧不是 X。全程只养一个计数器，扫完它就是答案。
回到题面这张 3×4 棋盘，逐格数船头
board=[[X,.,.,X],[.,.,.,X],[.,.,.,X]]，三行四列。(0,0) 是 X，上左都在界外，判成船头，计数到 1。(0,1)、(0,2) 空位跳过。(0,3) 是 X，上方界外、左方 (0,2) 是空位，又一个船头，计数到 2。(1,0) 到 (1,2) 空位跳过；(1,3) 是 X，上方 (0,3) 也是 X，是后半截，跳过。(2,0) 到 (2,2) 空位跳过；(2,3) 是 X，上方 (1,3) 也是 X，跳过。扫完全盘，计数器停在 2，也就是那艘单格船加一艘竖排三格船。
漏看左方那一列，横排战舰会被数成好几艘
每个格子只访问一次、外加常数次上左判断，时间 O(m·n)；只用一个计数变量、不开数组也不写回棋盘，空间 O(1)，正好压在进阶要求上。两个最容易栽的地方：只查上方、忘了左方，横排船的第二格、第三格因为上方不是 X，会被逐个误判成新船头，一艘横排船数成好几艘，横排的非头格正是靠「左方是 X」才被跳过的。还有第 0 行、第 0 列的边界，直接读 board[i-1][j] 或 board[i][j-1] 会越界，得先判 i＞0、j＞0 再看邻居。空棋盘或整盘没一个 X，计数器一直是 0，返回 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这把尺子:X 且「上不是 X、左不是 X」就计数。下面每一帧都在套它。
准备 · 全图待扫：蓝色是空位,灰色是还没扫到的战舰格 X。套路:一行一行、从左到右扫,只在 X 的「左上角」处计数。
扫描 · 遇到 X：扫到 (0,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是棋盘外边界,左方是棋盘外边界,所以 (0,0) 是一艘新战舰的左上角(变绿),战舰数加到 1。
扫描 · 空位：扫到 (0,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 1。
扫描 · 遇到 X：扫到 (0,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是棋盘外边界,左方是空位,所以 (0,2) 是一艘新战舰的左上角(变绿),战舰数加到 2。
扫描 · 遇到 X：扫到 (0,3) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正左方 (0,2) 也是 X,说明 (0,3) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
扫描 · 空位：扫到 (0,4),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 遇到 X：扫到 (1,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正上方 (0,0) 也是 X,说明 (1,0) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
扫描 · 空位：扫到 (1,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 空位：扫到 (1,2),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 空位：扫到 (1,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 遇到 X：扫到 (1,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是空位,左方是空位,所以 (1,4) 是一艘新战舰的左上角(变绿),战舰数加到 3。
扫描 · 空位：扫到 (2,0),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
扫描 · 空位：扫到 (2,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
扫描 · 遇到 X：扫到 (2,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是空位,左方是空位,所以 (2,2) 是一艘新战舰的左上角(变绿),战舰数加到 4。
扫描 · 空位：扫到 (2,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 4。
扫描 · 遇到 X：扫到 (2,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正上方 (1,4) 也是 X,说明 (2,4) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 4。
回放 · 四艘战舰：整张棋盘扫完。绿色的四格就是四艘战舰各自的左上角,数到 4 个,答案就是 4。灰色的都是被跳过的船身。
边界先想清:空盘 0、单 X 为 1、横竖混排按船头数。
两个高频追问:前提一旦放宽就回到岛屿数量;本解天然不改原图。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(m·n)，每个格子只看一次,外加常数次的上方、左方判断
- 空间：O(1)，只用一个计数变量,不开额外数组、也不改棋盘
易错点
面试追问把动画讲成自己的话
追问如果允许战舰相邻(挨着),这个 O(1) 解还成立吗?
追问面试官要求不修改 board,你的解满足吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
回旋镖的数量
LeetCode 447 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题