面试题13：机器人的运动范围

从坐标合法不等于能够到达开始

先预测：阈值k=1时，坐标(100,0)的数位和是1，看起来满足进入条件；机器人从(0,0)出发，真的一定能走到那里吗？若中间所有路径都被超阈值格子隔断，“格子合法”和“格子可达”还是同一件事吗？

“机器人的运动范围”给出m行n列网格，机器人从(0,0)开始，每次可向左、右、上、下移动一格。只有行坐标各位数字之和加列坐标各位数字之和不大于k，才能进入该格，问题要求统计机器人实际能够到达多少格。

这里的可达格子不是所有数位之和合格的坐标，而是从(0,0)沿四邻接路径逐步进入、且路径上每一步都通过约束的格子；因此它是搜索结果，不是对整张网格做坐标过滤后的结果。

与坐标大小不单调。作者示例中(35,37)的总数位和为18，阈值18时可进入；(35,38)为19，不能进入。十进制进位还会让99→100的数位和从18降为1，所以不能用坐标大小直接代替逐位计算。

满足数位约束只是“允许进入”，从起点存在一条全部合法的四邻接路径才是。所有允许格子可能包含与原点隔开的区域，不能扫描全图后把约束成立的格子直接相加。

把问题看成隐式图的连通分量

每个合法格子是一个顶点，上下左右合法邻居之间有边；题目求包含(0,0)的大小。无需预先构造所有边，只要从原点搜索时按坐标生成四个邻居。

作者使用递归。每次先检查边界、数位和与访问状态，首次到达就标记并计数1，再累加四个方向返回的数量。这也常被书中归入“回溯或广度优先搜索”的网格解法，但这里的visited不会在递归返回时撤销。

为什么不撤销？因为一个格子一旦从原点被发现，它已经属于目标连通分量，之后从其他路径再次到达只会重复计数和形成环。visited表示“全局已计数”，而上一题矩阵路径的visited表示“当前候选路径占用”；同名数组承载的语义不同，更新策略也相反。

忠实实现作者的四方向 DFS

数位和函数反复取末位并除以10。0的循环不执行，结果自然为0。入口先拒绝负阈值和非正行列，然后分配访问数组；从(0,0)开始，未实际到达的格子不会被扫描。

#include <cstddef>
#include <limits>
#include <stdexcept>
#include <vector>
 
int digitSum(int number) {
    int sum = 0;
    while (number > 0) {
        sum += number % 10;
        number /= 10;
    }
    return sum;
}
 
class RobotRange {
public:
    std::size_t movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows <= 0 || cols <= 0) return 0;
 
        const auto r = static_cast<std::size_t>(rows);
        const auto c = static_cast<std::size_t>(cols);
        if (r > std::numeric_limits<std::size_t>::max() / c) {
            throw std::length_error("grid is too large");
        }
 
        threshold_ = threshold;
        rows_ = rows;
        cols_ = cols;
        visited_.assign(r * c, 0);
        return dfs(0, 0);
    }
 
private:
    std::size_t dfs(int row, int col) {
        if (row < 0 || row >= rows_ ||
            col < 0 || col >= cols_) {
            return 0;
        }
        const auto pos =
            static_cast<std::size_t>(row) *
            static_cast<std::size_t>(cols_) +
            static_cast<std::size_t>(col);
        if (visited_[pos] ||
            digitSum(row) + digitSum(col) > threshold_) {
            return 0;
        }
 
        visited_[pos] = 1;
        return 1 + dfs(row - 1, col)
                 + dfs(row, col - 1)
                 + dfs(row + 1, col)
                 + dfs(row, col + 1);
    }
 
    int threshold_ = 0;
    int rows_ = 0;
    int cols_ = 0;
    std::vector<unsigned char> visited_;
};

标记必须发生在递归扩展之前。若先递归邻居、回来才标记，两个相邻合法格会互相调用形成无限递归。rows * cols在分配前也要防止整数乘法溢出；作者接收普通int且面试规模很小，工程接口不能默认任何尺寸都可安全相乘。

BFS 避免深递归栈

得到相同可达集合。它把合法且未访问的邻居放入队列，循环弹出并扩展。访问标记应在入队时设置，而不是出队时设置，否则同一格可能被多个父节点重复入队，占用额外内存。

#include <array>
#include <queue>
#include <utility>
 
std::size_t movingCountBfs(int threshold, int rows, int cols) {
    if (threshold < 0 || rows <= 0 || cols <= 0) return 0;
 
    std::vector<unsigned char> visited(
        static_cast<std::size_t>(rows) *
        static_cast<std::size_t>(cols), 0);
    std::queue<std::pair<int, int>> pending;
 
    auto tryPush = [&](int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||
            digitSum(row) + digitSum(col) > threshold) {
            return;
        }
        const auto pos =
            static_cast<std::size_t>(row) *
            static_cast<std::size_t>(cols) +
            static_cast<std::size_t>(col);
        if (visited[pos]) return;
        visited[pos] = 1;
        pending.emplace(row, col);
    };
 
    tryPush(0, 0);
    std::size_t count = 0;
    constexpr std::array directions{
        std::pair{-1, 0}, std::pair{1, 0},
        std::pair{0, -1}, std::pair{0, 1}
    };
 
    while (!pending.empty()) {
        const auto [row, col] = pending.front();
        pending.pop();
        ++count;
        for (const auto [dr, dc] : directions) {
            tryPush(row + dr, col + dc);
        }
    }
    return count;
}

DFS 与 BFS 都遍历同一连通分量，时间上界相同。DFS 代码贴近作者，递归深度在狭长网格或大可达区域中可能达到O(RC)并耗尽线程栈；BFS 使用堆上的队列，峰值取决于搜索前沿宽度，通常更适合大网格。

为什么首次发现一次恰好等于答案

先证明不会多计。代码只有在坐标位于边界内、数位和满足阈值且visited为假时才增加1；这个格又是从已可达父格的一个合法邻居扩展而来，所以每个被计数格都有一条从原点延伸出的合法路径。标记在计数前设置，之后所有重复到达都返回0，因此同一坐标最多贡献一次。

再证明不会漏计。对任意真正可达格，取一条从原点到它的合法路径。起点会被搜索发现；若路径前i个格已被发现，第i+1个格是其四邻居之一且满足约束，扩展该父格时就会被发现。按路径长度归纳，终点最终一定进入访问集合。于是算法计数集合与题目可达集合完全相同。

这个证明也解释了检查顺序：邻格必须由已可达格生成，不能在全图中独立判断；visited必须在首次发现时设置，不能等所有邻居处理完；计数只能和首次设置标记绑定，不能在每条入边上累加。

若入口格(0,0)不满足约束，搜索返回0。对于题目允许的非负阈值，原点数位和固定为0，因此总满足；负阈值在入口被作为非法参数直接返回0。这两个规则共同覆盖“机器人不能进入任何格”的情况。

四方向能否裁成只向右和向下

一些实现只扩展右、下两个方向，用网格对称性减少常数。这样的优化不能仅凭“起点在左上角”决定：可达性的定义允许四方向，而数位和在十进制进位处并不单调，某个格的可行路径是否总能改写成坐标单调路径需要独立证明。

作者源码明确探索上、左、下、右四方向，这是最直接符合题意的基线。它依靠全局访问标记去掉往返与环，因此即使多两个方向，每条合法格仍只扩展一次，渐进复杂度不会变。没有完成等价证明时，删方向属于改变搜索图，而不是普通微优化。

若采用两方向版本，应至少在大量行列尺寸与阈值上同四方向 BFS 交叉验证，并特别覆盖9→10、19→20、99→100等数位和突变边界。测试不能代替数学证明，但能暴露“看起来单调”的错误假设；书籍复刻以作者四方向契约为准。

类似地，也不能因为网格关于主对角线对称就只计算一半后乘2：矩形行列可能不同，对角线格不能重复计数，边界截断后的可达形状也需要单独处理。保持一次完整图遍历通常更清晰可靠。

数位和成本与缓存策略

若每次检查都重新对行列做除10循环，单次坐标判断成本与十进制位数D成正比，访问全网格的宽松上界是O(RC·D)。访问标记保证每个合法格最多扩展一次，但同一个非法邻居可能从多个方向被检查，常数仍受digitSum影响。

可以预先计算所有行与列的数位和：rowSums[r]和colSums[c]分别占O(R+C)空间，搜索时判断变成常数。顺序生成时还可利用digitSum(x+1)=digitSum(x)+1-9t，其中t是x末尾连续9的个数；例如99到100减去18再加1。

缓存是性能优化，不改变搜索语义。若网格很稀疏、阈值很小，只访问少量格子，预计算全部行列可能反而做了多余工作；可按需记忆坐标数位和。选择时比较可达区域大小、坐标位数和内存预算。

总体上，访问数组占O(RC)。DFS 另有最坏O(RC)调用栈，BFS 队列最坏也可容纳O(RC)格。若网格尺寸巨大而可达区域很小，可用哈希集合只记录已访问坐标，把空间改为与实际访问数V相关，但每次查找常数更高。

超大网格要区分逻辑尺寸与可分配尺寸

即使rows和cols各自能放入int，乘积也可能超过size_t或系统可分配内存。先转为无符号宽类型再检查rows > max / cols，才能避免乘法已经溢出后再判断；随后vector仍可能因内存不足抛出异常，接口要决定向上传播还是转成错误结果。

当逻辑网格极大但阈值很小，密集R×C访问位图不合理。哈希集合可只存实际发现的坐标，队列也只含搜索前沿；坐标对可编码为64位键或结构体哈希。此时复杂度按实际可达数V描述更有意义，时间约为O(V·D)的平均哈希成本，空间O(V)。

稀疏结构不等于可以取消边界。邻居row+1、col+1在最大整数处可能溢出，先确认当前坐标严格小于末边界再加一最安全；负方向则先检查大于0。作者使用小型int测试没有触发这些问题，通用接口仍应把坐标算术纳入契约。

返回类型也应容纳最大可能答案。int在超大网格中可能装不下格子数，现代实现使用size_t或明确宽度的无符号整数；序列化、跨语言接口再约定上限。正确搜索后把计数截断回32位仍是错误结果。

为什么不能只统计所有满足阈值的格子

坐标数位和并不随坐标单调增加，十进制进位会产生远处的低数位和“岛屿”。阈值很小时，原点附近可达区域可能被一整条不合法带阻断；阻断带另一侧即使有满足阈值的格子，机器人也无法穿越。

因此条件应按顺序理解：先从一个已可达格沿边走到邻格，再检查邻格是否允许进入。全图过滤只回答“哪些顶点合法”，搜索才回答“哪些合法顶点与原点连通”。官方问题问后者。

官方九组测试锁定坐标与尺寸边界

作者Test1验证阈值5、10行10列返回21，Test2验证阈值15、20行20列返回359。单行测试k=10, 1×100返回29而1×10返回10，能发现只用个位或误认为数位和单调的实现。

单列测试k=15, 100×1返回79，10×1返回10；它们与单行共同验证行列计算对称。1×1在阈值15和0时都返回1，因为原点数位和为0；负阈值-10返回0。

#include <cassert>
 
void testRobotRange() {
    RobotRange solver;
    assert(solver.movingCount(5, 10, 10) == 21);
    assert(solver.movingCount(15, 20, 20) == 359);
    assert(solver.movingCount(10, 1, 100) == 29);
    assert(solver.movingCount(10, 1, 10) == 10);
    assert(solver.movingCount(15, 100, 1) == 79);
    assert(solver.movingCount(15, 10, 1) == 10);
    assert(solver.movingCount(15, 1, 1) == 1);
    assert(solver.movingCount(0, 1, 1) == 1);
    assert(solver.movingCount(-10, 10, 10) == 0);
}
 
void crossCheckSearches(int k, int rows, int cols) {
    RobotRange dfs;
    assert(dfs.movingCount(k, rows, cols) ==
           movingCountBfs(k, rows, cols));
}

随机小网格可以让 DFS 与 BFS 互为预言机，再用独立显式图遍历核查。还应重复调用同一个RobotRange对象，确认每次入口重新初始化visited、阈值和尺寸；成员状态残留会让第二次调用少计格子。

本章练习

（边界条件）

概念说明

从起点 (0,0) 开始回溯或广度优先搜索，每次检查行列坐标的数位之和是否不超过阈值。统计所有可达的格子，即机器人能到达的格子范围。

本章回顾

1. 机器人的运动范围是从原点可达且坐标数位和不超过阈值的连通区域。
2. 数位之和按十进制各位计算，随坐标增长并不单调。
3. 合法格不一定是可达格，必须从(0,0)进行图搜索。
4. DFS 和 BFS 都可遍历同一连通分量，访问标记在首次发现时永久设置。
5. 本题visited表示全局已计数，不能像矩阵路径回溯那样撤销。
6. 普通实现最坏访问RC个格，空间为O(RC)，递归DFS还有栈深风险。
7. 数位和可按需计算、预计算行列缓存或利用进位关系增量更新。
8. 官方九组测试覆盖二维、单行、单列、单格、零阈值与非法阈值。

名词解释