LeetCode 剑指 Offer 13. 机器人的运动范围
目录
题目描述
题意分析
一个机器人站在
m行n列网格的左上角(0, 0)，每次只能上下左右挪一格，并且不能踏进「行下标各位数字之和加上列下标各位数字之和大于k」的格子。问它总共能走到多少个格子。最容易读错的地方是「能到达」三个字。题目问的不是网格里有多少个格子满足数位和条件，而是有多少个格子机器人真的走得过去。这两者不等价：数位和条件在网格上会切出一些孤岛，比如某一整行整列都超限时，后面即使有合法格子也被隔断了。这个区别决定了不能简单地二重循环计数。
第二个信号是网格规模上界只有一百量级，所以数位和条件虽然长得像数论题，实际上完全允许对每个格子逐一判定，没必要去找闭式规律。
边界要想清楚两处：
k可以为0，此时只有(0, 0)一个格子合法，答案是1；下标从0开始，0的数位和是0，求数位和的辅助函数在传入0时必须返回0而不是死循环或返回别的值。
解法：广度优先搜索可达格子
核心思路
先看那个诱人的错误暴力：双重循环遍历所有格子，凡是数位和不超过
k就计数。它 $O(mn)$ 且写起来最短，但会把被隔断的合法格子也算进去。举个具体的反例，当k = 15时，行19或列19的数位和已经是10，会形成一道墙，墙后面某些数位和合格的格子其实走不到，这种写法会多算。所以瓶颈不在于判定单个格子，而在于必须刻画「连通」。既然是从固定起点出发、沿四邻接扩散，那就是标准的图上可达性问题：把每个合法格子看成一个顶点，相邻的合法格子之间连边，答案就是起点所在连通块的大小。
用队列做逐层扩散，就把「可达」这件事变成了一个显式的过程：起点先入队，然后不断取出一个已确认可达的格子，检查它的四个邻居，凡是没越界、没访问过、数位和又合格的，就确认它也可达并入队。
不变量是：任意时刻，队列里以及已经出队的所有格子，恰好构成「已被确认从
(0, 0)可达且合法」的集合，且这个集合与visited中被标记为true的格子一一对应。 由于每个格子在入队的同一瞬间就被标记，它永远不会第二次入队，因此总出队次数就等于连通块大小，直接累加即可。
解题步骤
- 开一个
m行n列的visited数组，再开一个容量为m * n的数组当队列。容量取满是因为最坏情况下所有格子都可达，这样就不必考虑扩容。- 处理起点：题目里
k >= 0而起点数位和恒为0，所以起点必然合法；代码里保留一次显式检查，是为了让「起点不合法就返回0」这条语义写在明面上，换成k可能为负的变体时不用改结构。- 把
(0, 0)标记为已访问并入队。标记必须与入队同时发生，而不是等出队时再标记，否则同一个格子可能从上方和左方分别被推入两次，最终计数翻倍。- 主循环每次取出队首，
ans加一。因为出队意味着这个格子的可达性已经板上钉钉，计数放在出队处最直观。- 对四个方向逐一试探，依次过滤三类情况：行列越界、已经访问过、数位和超过
k。前两类是搜索框架的常规守卫，第三类是本题特有的通行条件——非法格子既不能计数，也不能当作中转站继续往外扩，所以必须在入队前就拦掉。- 通过全部检查的邻居标记并入队。循环在队列空时自然终止，此时
ans就是答案。- 数位和函数用不断取模除十的写法。循环条件是
num > 0，传入0时一次都不进循环，直接返回0，正好符合下标从零开始的语义。以
m = 3、n = 2、k = 1走一遍：先把六个格子的数位和列出来，(0,0)是0，(0,1)是1，(1,0)是1，(1,1)是2，(2,0)是2，(2,1)是3，所以只有前三个不超过k = 1。搜索开始：visited[0][0]置真，队列为[(0,0)]，ans = 0。第一次出队(0,0)，ans变1；试四个方向，向下得(1,0)，不越界、未访问、数位和1 <= 1，标记并入队；向上得(-1,0)，越界跳过；向右得(0,1)，数位和1 <= 1，标记并入队；向左得(0,-1)，越界跳过。队列变成[(0,0),(1,0),(0,1)]。第二次出队(1,0)，ans变2；向下得(2,0)，数位和2 > 1，跳过；向上得(0,0)，已访问；向右得(1,1)，数位和2 > 1，跳过；向左越界。队列不变。第三次出队(0,1)，ans变3；向下得(1,1)，数位和超限；向上越界；向右得(0,2)，列越界（n = 2）；向左得(0,0)，已访问。队列耗尽，循环结束，返回3。
代码实现
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int[][] queue = new int[m * n][2];
int head = 0;
int tail = 0;
int ans = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
if (digitSum(0) + digitSum(0) > k) {
return 0;
}
visited[0][0] = true;
queue[tail++] = new int[]{0, 0};
while (head < tail) {
int[] cell = queue[head++];
ans++;
// 只有真正可达且合法的格子才入队，避免重复计数。
for (int[] dir : dirs) {
int row = cell[0] + dir[0];
int col = cell[1] + dir[1];
if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
continue;
}
if (digitSum(row) + digitSum(col) > k) {
continue;
}
visited[row][col] = true;
queue[tail++] = new int[]{row, col};
}
}
return ans;
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
}
func movingCount(m int, n int, k int) int {
visited := make([][]bool, m)
for i := 0; i < m; i++ {
visited[i] = make([]bool, n)
}
dirs := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
queue := [][]int{{0, 0}}
visited[0][0] = true
ans := 0
for head := 0; head < len(queue); head++ {
cell := queue[head]
ans++
// 只有真正可达且合法的格子才入队，避免重复计数。
for _, dir := range dirs {
row := cell[0] + dir[0]
col := cell[1] + dir[1]
if row < 0 || row >= m || col < 0 || col >= n || visited[row][col] {
continue
}
if digitSum(row)+digitSum(col) > k {
continue
}
visited[row][col] = true
queue = append(queue, []int{row, col})
}
}
return ans
}
func digitSum(num int) int {
sum := 0
for num > 0 {
sum += num % 10
num /= 10
}
return sum
}
复杂度分析
- 时间复杂度：$O(mn \log(\max(m, n)))$，每个格子最多入队一次、出队一次，出队时固定检查四个邻居；每次检查要算两个下标的数位和，代价与下标的十进制位数成正比，即 $O(\log(\max(m, n)))$。
- 空间复杂度：$O(mn)$，
visited数组固定占 $mn$，队列在最坏情况（全部格子可达）下也会存满 $mn$ 个坐标，两者同阶。
关键点总结
- 「满足条件的格子数」和「从起点可达的格子数」是两个不同的问题，读题时看到「能够到达」就必须切到搜索，不能退化成计数循环。这类措辞陷阱在网格题里非常常见。
- 标记访问的时机要放在入队处而不是出队处。放在出队处时，同一个格子可能被多个邻居同时推进队列，导致重复计数与队列膨胀，这是广搜最经典的写错点。
- 通行条件必须在入队前判定，因为非法格子不仅不能计数，也不能作为中转继续扩散。把「能否站上去」和「能否穿过去」区分清楚，是所有带障碍搜索题的共同要求。
- 队列容量可以按理论上界一次开满，避免动态扩容，这在网格类题里是零成本的简化。
- 面试视角：先主动说出「二重循环计数」的错法并给出被隔断的反例，能立刻显示你抓住了题目的真正难点；很多人正是因为样例太小没暴露差异而栽在这里。
- 面试视角：常见追问是「能不能只向右和向下扩展」。可以答：本题的合法区域恰好保证了从起点只用右和下就能到达任一可达格子，所以简化写法碰巧正确，但这依赖数位和函数的特殊单调性质，不是通用结论，面试中最好写四方向的稳妥版本并说明取舍。
易错点总结
- 错误写法：直接二重循环统计所有数位和不超过
k的格子。用例m = 30、n = 30、k = 15→ 行或列取到19时数位和已达10，形成隔断带，带外那些看似合格的格子其实不可达，结果偏大。- 错误写法：出队时才标记
visited。用例m = 3、n = 3、k = 4→ 格子(1,1)会被(0,1)和(1,0)各推入队列一次，ans多加一，同时队列可能超出预分配容量而越界。- 错误写法：把数位和检查写在出队之后而不是入队之前。用例
m = 3、n = 2、k = 1→ 数位和为2的(1,1)也会进队，虽然出队时被跳过不计数，但它的邻居仍可能被错误扩展，等于允许穿墙。- 错误写法：数位和函数写成
while (num >= 0)。用例任意下标 →num减到0后除十仍是0，条件恒成立，陷入死循环。- 错误写法：把行列边界判反，写成
row >= n || col >= m。用例m = 3、n = 2→ 行下标2会被误判为越界而丢弃，列下标2反而被放行，随即数组下标越界崩溃。- 错误写法：把两个坐标的数位和写成
digitSum(row + col)。用例m = 20、n = 20、k = 10中的格子(9, 9)→ 正确的数位和是9 + 9 = 18，超过k应当禁止进入；而该写法算的是digitSum(18) = 9，误判为合法，可达区域被放大。- 错误写法：
ans在入队时累加而出队时不加，同时又漏了入队即标记。用例任意可达区域 → 与重复入队叠加后计数偏大，且两处逻辑分散在不同位置，调试时极难定位。- 错误写法：认为
k = 0时无解并返回0。用例m = 2、n = 2、k = 0→ 起点(0,0)数位和恰为0，是合法且可达的，正确答案是1。- 错误写法：
visited只开一维或按m * n展平却用错了行列换算公式。用例m = 3、n = 2→ 索引row * m + col与row * n + col混用会让不同格子映射到同一下标，可达区域被误判为已访问，结果偏小。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 200. 岛屿数量 | 中等 | 统计连通块个数，需要对每个未访问点重新起搜 |
| 695. 岛屿的最大面积 | 中等 | 求所有连通块大小的最大值，而非固定起点的一块 |
| 733. 图像渲染 | 简单 | 通行条件由原始颜色决定，且需就地改写网格 |
| 1091. 二进制矩阵中的最短路径 | 中等 | 求最短步数而非可达数量，且是八方向扩展 |
| 994. 腐烂的橘子 | 中等 | 多源同时扩散并按层计时，需判断残留不可达点 |
| 130. 被围绕的区域 | 中等 | 从边界反向起搜，用可达性反推被包围区域 |
| 剑指 Offer 12. 矩阵中的路径 | 中等 | 找特定字符路径，需要回溯撤销访问标记 |