CS-Notes 剑指 Offer 题解：机器人的运动范围——用 DFS 求解可达格子数

本篇基于 CS-Notes 剑指 Offer 题解中的《13. 机器人的运动范围》一文展开，完整讲解这道经典搜索题的题目背景、深度优先搜索（DFS）求解思路与一份带数位和预处理的完整 Java 实现，并补充代码逐段解读、边界正确性细节与时间/空间复杂度分析。读完本文，你应能独立写出该问题的 DFS/BFS 两种解法，并理解"预处理一维数位和"这一优化技巧的由来与适用场景。

题目描述与示例

地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

例如，当 k 为 18 时，机器人能够进入方格 (35,37)，因为 3+5+3+7=18。但是，它不能进入方格 (35,38)，因为 3+5+3+8=19。请问该机器人能够达到多少个格子？

题目给出的示例中，机器人恰好停在"数位和等于阈值"的边界上——等于 k 可以进入，大于 k 才能进入就非法。这一点决定了后续代码中判断条件必须写成 digitSum[r][c] > threshold 才返回，而不是 >= threshold。

这道题在 CS-Notes 的 剑指 Offer 题解 - 目录 中被归入"搜索"分类，与 12. 矩阵中的路径 同属一类网格搜索问题，但区别在于：第 12 题要求从任意格子出发寻找匹配字符串的路径（回溯法），而本题只需统计以 (0, 0) 为起点的连通可达区域大小（普通 DFS），不需要在每次搜索结束后清除局部状态。

解题思路：为什么是 DFS 而不是回溯

原始文档给出的核心思路是：

使用深度优先搜索（Depth First Search，DFS）方法进行求解。回溯是深度优先搜索的一种特例，它在一次搜索过程中需要设置一些本次搜索过程的局部状态，并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态，虽然还是有可能设置一些全局状态。

可以进一步把这句话落到本题的具体结构上：

• 状态空间：m × n 个格子，每个格子要么可达、要么不可达。机器人从 (0, 0) 出发，每次移动一格，因此可达格子集合恰好是"所有数位和 ≤ k 的格子中，与 (0, 0) 四方向连通的连通分量"。
• 为什么不会重复计数：用一个 boolean[][] marked 数组记录"是否访问过"。一旦某格子被标记，后续从任何方向进入都会直接剪枝，所以每个格子至多被"处理"一次，统计值 cnt 不会重复累加。
• DFS 与回溯的差异体现在状态管理上：本题的 marked 属于全局状态，整个搜索过程只做一次标记、永不清除；而回溯法（如矩阵中的路径）需要在返回时把本次搜索设置的标记清除，以便同一路径上的其他分支能重新利用这些格子。理解这一差异是区分两类网格搜索题的关键。

完整解法代码

以下是原始文档中给出的完整 Java 实现，原样保留：

private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
private int cnt = 0;
private int rows;
private int cols;
private int threshold;
private int[][] digitSum;

public int movingCount(int threshold, int rows, int cols) {
    this.rows = rows;
    this.cols = cols;
    this.threshold = threshold;
    initDigitSum();
    boolean[][] marked = new boolean[rows][cols];
    dfs(marked, 0, 0);
    return cnt;
}

private void dfs(boolean[][] marked, int r, int c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])
        return;
    marked[r][c] = true;
    if (this.digitSum[r][c] > this.threshold)
        return;
    cnt++;
    for (int[] n : next)
        dfs(marked, r + n[0], c + n[1]);
}

private void initDigitSum() {
    int[] digitSumOne = new int[Math.max(rows, cols)];
    for (int i = 0; i < digitSumOne.length; i++) {
        int n = i;
        while (n > 0) {
            digitSumOne[i] += n % 10;
            n /= 10;
        }
    }
    this.digitSum = new int[rows][cols];
    for (int i = 0; i < this.rows; i++)
        for (int j = 0; j < this.cols; j++)
            this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j];
}

下面按方法逐段解读其设计意图。

movingCount：搜索入口

• 先把 rows、cols、threshold 三个参数保存到实例字段，避免在递归中反复传参；
• 调用 initDigitSum() 预计算所有格子的数位和（见下文）；
• 分配 marked 访问标记数组，从 (0, 0) 启动一次 DFS，最终返回计数器 cnt。

dfs：剪枝顺序与递归主体

if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c])
    return;

第一层剪枝是边界与重访检查：新坐标超出网格、或格子已被标记过，直接返回。注意这里把 marked 检查放在最前面——由于每个格子只会被合法处理一次，这一条同时承担了"防止重复计数"和"终止递归"两个职责。

marked[r][c] = true;
if (this.digitSum[r][c] > this.threshold)
    return;
cnt++;

第二层是阈值剪枝：先把格子标记为已访问，再判断数位和是否超标。这个顺序是一个容易忽视但重要的细节：

1. 若先判断阈值再标记，一个"数位和超标"的格子会在搜索过程中被相邻格子反复尝试进入，每次都重新计算一次阈值判断，虽然结果仍正确，但产生了冗余检查；
2. 先标记再判断，使得每个不合法格子也只会被"探测"一次，其四方向邻居再也不会对它发起新的 DFS 调用。从源码结构看，marked 在这里实际上同时覆盖了"合法可达"和"已确认不可达"两类格子，整个搜索的调用总次数因此被严格控制。

最后 cnt++ 只发生在阈值检查通过之后，即只有真正进入的格子才计入答案；随后按 next 表中的四个方向（左、右、上、下）继续递归。

next 方向表：把四方向移动参数化

{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} 是网格题的标准写法：每一行是一个 (dr, dc) 位移向量，递归时用 r + n[0]、c + n[1] 生成邻居坐标。相比写死四个 if 分支，这种写法把"移动规则"与"搜索逻辑"解耦——如果题目变成八方向移动，只需改这张表。

关键优化：一维数位和预处理

原始文档中 initDigitSum 的实现值得单独展开，因为它是这份解法相比朴素写法（每个格子调用一次 digitSum(r) + digitSum(c)）的核心优势所在。

其思路分两步：

1. 先算一维表：digitSumOne[i] 存单个数字 i 的各位数字之和，长度取 max(rows, cols)，用"取余 + 整除"的循环剥离每一位（n % 10 取末位、n /= 10 去掉末位）；
2. 组合成二维表：格子的数位和 = 行坐标数位和 + 列坐标数位和，因此 digitSum[i][j] = digitSumOne[i] + digitSumOne[j]，一次查表即得。

这样设计的好处可以从两个维度理解：

• 时间上：一维表本身长度为 O(max(m, n))，每个元素的剥离循环与坐标位数 d 成正比，开销可忽略；二维表填充是 O(m·n) 的纯加法，总体预处理为 O(m·n)。而朴素写法下，DFS 过程中每次进入格子都要现算两次数位和，常数因子更高，且重复计算。
• 空间换时间的典型形态：额外付出 O(m·n) 的 digitSum 数组，换取 DFS 中每格 O(1) 的阈值判断。对于本题"统计全量可达格子"的目标，这个交换是划算的——搜索本身最坏也是 O(m·n)，预处理没有让整体复杂度升档。

需要注意其适用前提：digitSumOne 只算到 max(rows, cols) - 1，因此该实现默认行、列坐标都小于该长度上限，这正是数组下标本身所保证的，不存在越界问题。

边界情形与正确性细节

结合代码可以梳理出几个容易出错的边界：

• (0, 0) 本身不合法：若 digitSum[0][0] > threshold（例如 k 很小），DFS 会把 (0, 0) 标记后直接返回，cnt 保持 0，函数正确返回 0，不需要特殊处理。
• 等于阈值可进入：判断式是 > threshold 时返回，与题目示例中 (35, 37) 数位和恰好 18 可进入一致。
• visited 数组的维度：marked 是 rows × cols 的全局数组，一次搜索全程共享；这与回溯题中"标记-清除"的用法形成对照，也再次印证了原始文档"普通 DFS 不需要回溯状态"的说法。
• 递归深度的实践限制：最坏情况下可达格子呈一条细长蛇形路径，递归深度可达 O(m·n)，在 m、n 较大时有栈溢出风险。若目标环境是超大网格，可改写为显式队列的 BFS（广度优先搜索）版本：入队前判断边界、标记与阈值，逻辑与 DFS 完全同构，仅把递归换成循环，即可消除深度问题。就本题在剑指 Offer 中的常规数据规模而言，DFS 递归版本已经足够。

复杂度分析

• 时间：预处理 initDigitSum 为 O(m·n)（一维部分更低阶）；DFS 阶段由于每个格子至多被标记一次，dfs 的总调用次数上界为 O(4·m·n)，即 O(m·n)。整体时间复杂度为 O(m·n)。
• 空间：marked 与 digitSum 各占 O(m·n)，digitSumOne 占 O(max(m, n))，另有 O(递归深度) 的调用栈，最坏 O(m·n)。整体空间复杂度为 O(m·n)。
• 最坏情形的直观理解：当 k 大到足够覆盖整个网格时，cnt 恰好等于 m·n，搜索遍历所有格子；当 k 很小时，搜索被阈值剪枝快速限制在 (0, 0) 附近的小区域内，实际运行远低于上界。

小结与相关题目

• 本题的解法骨架是"网格 + 方向表 + visited 标记 + DFS"，与 12. 矩阵中的路径 共享同一套框架，区别只在于是否需要回溯清除状态：路径匹配类问题需要回溯，连通区域计数类问题不需要。
• 原始文档中"回溯是深度优先搜索的特例"这一论断，是区分 剑指 Offer 题解 - 目录 中"搜索"分类下各题目的有效判据：先问"搜索结束后要不要还原状态"，再决定套用哪种模板。
• 完整的 Java 实现以实例字段承载阈值、行列数与预处理的数位和表，配合 next 方向表与 marked 剪枝，构成了一份可直接提交、可直接阅读的参考解法；如需应对超大网格，可按上文思路改写为 BFS 迭代版本。