尧图网页设计 
LeetCode LCR 130 衣橱整理机器人的运动范围DFS 与 BFS 完整题解与源码剖析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中 《LCR 130. 衣橱整理》 题解文档为核心围绕机器人从矩阵左上角出发、按数位和约束移动统计可到达格子数这一经典搜索问题系统讲解数位和增量公式推导、可达解连通性分析、深度优先搜索DFS与广度优先搜索BFS两种解法并结合仓库内 Python / Java / C 三语言实现与测试用例给出可直接运行、可直接套用的完整解题方案。读完本文你将掌握如何用增量式计算替代逐位求和来优化数位和计算理解为何本题只需向右、向下两个方向搜索并能在面试中熟练写出 DFS 与 BFS 两种版本的代码。一、题目背景从机器人的运动范围到衣橱整理LCR 130「衣橱整理」是《图解算法数据结构》leetbook_ioa中的一道高频搜索题其原始形态是剑指 Offer 13「机器人的运动范围」。仓库中两份题解文档相互对应leetbook_ioa/docs/LCR 130. 衣橱整理.md本文主体sword_for_offer/docs/剑指 Offer 13. 机器人的运动范围.md同名姊妹题问题描述家居整理师将待整理衣物划分为m x n的二维矩阵从左上角(0, 0)出发每次可向右或向下移动一格若某格子行索引和列索引的数位之和大于给定目标值cnt则不能进入。求机器人能到达的格子数量。该题与仓库中 LCR 129. 字母迷宫原矩阵中的路径同属搜索 回溯家族但本题不需要回溯——因为目标是统计连通区域大小而非寻找特定路径访问过的格子无需还原。这一点在后文 DFS 实现中体现为标记后不再撤销。本文中的cnt对应仓库原题文档剑指 Offer 13 题解及代码中的k二者含义一致均为数位和上限。二、前置工作一数位之和计算与增量公式2.1 基础数位和计算设一数字x向下取整除法符号//求余符号%则有x % 10得到x的个位数字x // 10令x的十进制数向右移动一位即删除个位数字。通过循环累加即可求得数位和s封装函数如下def sums(x): s 0 while x ! 0: s x % 10 x x // 10 return sint sums(int x) { int s 0; while (x ! 0) { s x % 10; x x / 10; } return s; }int sums(int x) { int s 0; while (x ! 0) { s x % 10; x x / 10; } return s; }2.2 数位和增量公式核心优化由于机器人每次只能移动一格即只能从x运动至x ± 1每次只需计算相邻两数的数位和增量。本题约束1 ≤ n, m ≤ 100坐标最大为 99数位和不超过 18以下公式仅在此范围内成立。设x的数位和为s_xx 1的数位和为s_{x1}当(x 1) % 10 0发生进位时s_{x1} s_x - 8。例如19 → 20数位和由10变为210 - 8 2当(x 1) % 10 ! 0无进位时s_{x1} s_x 1。例如1 → 2数位和由1变为2。用三元表达式写作s_x 1 if (x 1) % 10 else s_x - 8(x 1) % 10 ! 0 ? s_x 1 : s_x - 8;(x 1) % 10 ! 0 ? s_x 1 : s_x - 8;这一技巧使得代码在每次递归/迭代中以O(1)常数时间获得下一个格子的数位和避免了对每个新坐标重新执行while循环求和这是本解性能优秀的关键细节也直接体现在仓库全部六份实现代码中。三、前置工作二可达解分析3.1 解的几何形态等腰直角三角形簇根据增量公式可知数位和每逢进位突变一次个位由 9 进到 0 时数位和骤降 8。因此矩阵中满足数位和约束的解其几何形状形如多个等腰直角三角形每个三角形的直角顶点位于0, 10, 20, ...等数位和突变的矩阵索引处。原文档附有n, m 20、cnt ∈ [6, 19]的系列示意图直观展示了可达解、不可达解、非解随cnt增大的连通性变化可在 leetbook_ioa/docs/LCR 130. 衣橱整理.md 中查看。3.2 可达解与不可达解不可达解三角形内的格子虽然都满足数位和要求但机器人每步只能移动一个单元格而相邻三角形之间不一定连通因此机器人不一定能到达称之为不可达解可达解可实际到达的解本题统计的就是可达解的数量。3.3 关键推论只需向右和向下搜索根据可达解的结构和连通性可以证明机器人仅通过向右和向下移动即可访问所有可达解三角形内部全部连通易证两三角形连通处若某三角形内的解为可达解则必与其左边或上边的三角形连通即相交机器人必可从左边或上边走进此三角形。因此DFS / BFS 中只需要探索下方、右方两个方向无需向四个方向搜索这也避免了向上、向左移动可能产生的重复路径进一步降低了分支因子。仓库中的实现全部遵循这一结论例如 sword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s1.py 中仅递归调用dfs(i 1, j, ...)与dfs(i, j 1, ...)两个方向。四、方法一深度优先遍历DFS深度优先搜索可理解为暴力模拟机器人在矩阵中的所有路径通过递归先朝一个方向搜到底再回溯至上个节点沿另一方向继续搜索。剪枝可行性剪枝搜索中遇到数位和超出目标值、或该元素已被访问立即返回不再深入。4.1 算法解析递归参数当前元素的矩阵行列索引i、j以及两者的数位和si、sj终止条件当 ① 行列索引越界或② 数位和si sj超出目标值cnt或③ 当前元素已访问过时返回0不计入可达解递推工作标记当前单元格将索引(i, j)存入集合visited代表已访问搜索下一单元格计算当前元素下方、右方两元素的数位和开启下层递归回溯返回值返回1 右方搜索的可达解总数 下方搜索的可达解总数即从本单元格出发递归搜索到的可达解总数。4.2 代码实现Java / C 代码中visited为辅助矩阵Python 中为set集合。class Solution: def wardrobeFinishing(self, m: int, n: int, cnt: int) - int: def dfs(i, j, si, sj): if i m or j n or cnt si sj or (i, j) in visited: return 0 visited.add((i, j)) return 1 dfs(i 1, j, si 1 if (i 1) % 10 else si - 8, sj) dfs(i, j 1, si, sj 1 if (j 1) % 10 else sj - 8) visited set() return dfs(0, 0, 0, 0)class Solution { int m, n, cnt; boolean[][] visited; public int wardrobeFinishing(int m, int n, int cnt) { this.m m; this.n n; this.cnt cnt; this.visited new boolean[m][n]; return dfs(0, 0, 0, 0); } public int dfs(int i, int j, int si, int sj) { if (i m || j n || cnt si sj || visited[i][j]) return 0; visited[i][j] true; return 1 dfs(i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj) dfs(i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8); } }class Solution { public: int wardrobeFinishing(int m, int n, int cnt) { vectorvectorbool visited(m, vectorbool(n, 0)); return dfs(0, 0, 0, 0, visited, m, n, cnt); } private: int dfs(int i, int j, int si, int sj, vectorvectorbool visited, int m, int n, int cnt) { if (i m || j n || cnt si sj || visited[i][j]) return 0; visited[i][j] true; return 1 dfs(i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj, visited, m, n, cnt) dfs(i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8, visited, m, n, cnt); } };仓库中可直接运行的同构实现方法名movingCount参数名ksword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s1.pysword_for_offer/codes/java/sfo_13_range_of_motion_of_a_robot_s1/sfo_13_range_of_motion_of_a_robot_s1.javasword_for_offer/codes/cpp/sfo_13_range_of_motion_of_a_robot_s1/sfo_13_range_of_motion_of_a_robot_s1.cpp五、方法二广度优先遍历BFSBFS 与 DFS 目标一致——遍历整个矩阵区别仅在于搜索顺序DFS 朝一个方向走到底再回退BFS 则按平推的方式逐层向外搜索通常借助队列实现。5.1 算法解析初始化将机器人初始点(0, 0)及其数位和(0, 0, 0, 0)加入队列queue迭代终止条件queue为空代表已遍历完所有可达解迭代工作单元格出队弹出队首单元格的索引与数位和作为当前搜索单元格判断是否跳过若 ① 行列索引越界或② 数位和超出目标值cnt或③ 当前元素已访问过执行continue标记当前单元格将索引(i, j)存入集合visited单元格入队将当前元素下方、右方单元格的索引与数位和加入queue返回值集合visited的长度len(visited)即可达解数量。Java / C 使用辅助变量res计数Python 直接返回集合长度。5.2 代码实现class Solution: def wardrobeFinishing(self, m: int, n: int, cnt: int) - int: queue, visited [(0, 0, 0, 0)], set() while queue: i, j, si, sj queue.pop(0) if i m or j n or cnt si sj or (i, j) in visited: continue visited.add((i, j)) queue.append((i 1, j, si 1 if (i 1) % 10 else si - 8, sj)) queue.append((i, j 1, si, sj 1 if (j 1) % 10 else sj - 8)) return len(visited)class Solution { public int wardrobeFinishing(int m, int n, int cnt) { boolean[][] visited new boolean[m][n]; int res 0; Queueint[] queue new LinkedListint[](); queue.add(new int[] { 0, 0, 0, 0 }); while (queue.size() 0) { int[] x queue.poll(); int i x[0], j x[1], si x[2], sj x[3]; if (i m || j n || cnt si sj || visited[i][j]) continue; visited[i][j] true; res; queue.add(new int[] { i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj }); queue.add(new int[] { i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8 }); } return res; } }class Solution { public: int wardrobeFinishing(int m, int n, int cnt) { vectorvectorbool visited(m, vectorbool(n, 0)); int res 0; queuevectorint que; que.push({ 0, 0, 0, 0 }); while (que.size() 0) { vectorint x que.front(); que.pop(); int i x[0], j x[1], si x[2], sj x[3]; if (i m || j n || cnt si sj || visited[i][j]) continue; visited[i][j] true; res; que.push({ i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj }); que.push({ i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8 }); } return res; } };仓库中 BFS 版本的可运行实现sword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s2.pysword_for_offer/codes/java/sfo_13_range_of_motion_of_a_robot_s2/sfo_13_range_of_motion_of_a_robot_s2.javasword_for_offer/codes/cpp/sfo_13_range_of_motion_of_a_robot_s2/sfo_13_range_of_motion_of_a_robot_s2.cpp六、复杂度分析设矩阵行列数分别为M, N时间复杂度 O(MN)最差情况下机器人遍历矩阵中所有单元格每个格子至多被访问一次复杂度为 O(MN)空间复杂度 O(MN)最差情况下visited内存储矩阵所有单元格的索引占用 O(MN) 额外空间。两种方法在最坏情况下的时间、空间复杂度完全一致实际选择取决于面试场景——DFS 代码更短、递归语义直观BFS 则避免了深递归可能带来的系统栈开销。七、仓库源码验证与测试用例仓库为本题提供了完整的解题代码 驱动测试结构可在本地直接编译运行验证Python 实现文件末尾附有# Test Case 与 Driver Code例如 sfo_13_range_of_motion_of_a_robot_s1.py 使用测试用例m 2, n 3, k 1调用slt.movingCount(m, n, k)并打印结果Java 实现main()方法中构造同样的测试用例并System.out.println(res)见 sfo_13_range_of_motion_of_a_robot_s1.javaC 实现main()中以Solution *slt new Solution()调用并cout res见 sfo_13_range_of_motion_of_a_robot_s2.cpp。手动验证测试用例对m 2, n 3, k 1的 2×3 矩阵坐标数位和满足si sj ≤ 1的格子为(0,0)、(0,1)、(1,0)共3个。可见 DFS、BFS 两版代码在该用例下应输出3读者可据此自测以确认理解正确。八、小结LCR 130「衣橱整理」是搜索与剪枝的经典入门题其核心方法论可归纳为三条数位和增量公式以 O(1) 代价获得相邻格子的数位和是性能关键可达性分析借助等腰直角三角形簇的连通性结论把四方向搜索降为仅向右、向下直接减小搜索空间DFS / BFS 双模板DFS 用递归 集合标记BFS 用队列 集合标记二者复杂度相同可随面试场景灵活切换。如需复习同类搜索题可对照阅读 LCR 129. 字母迷宫需回溯还原标记的矩阵路径搜索体会两者在标记是否需要还原上的本质差异仓库中全部题解与代码的组织方式见 README.md。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode LCR 130 衣橱整理（机器人的运动范围）：DFS 与 BFS 完整题解与源码剖析
LeetCode LCR 130 衣橱整理机器人的运动范围DFS 与 BFS 完整题解与源码剖析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇技术指南以 LeetCode-Book 仓库中 《LCR 130. 衣橱整理》 题解文档为核心围绕机器人从矩阵左上角出发、按数位和约束移动统计可到达格子数这一经典搜索问题系统讲解数位和增量公式推导、可达解连通性分析、深度优先搜索DFS与广度优先搜索BFS两种解法并结合仓库内 Python / Java / C 三语言实现与测试用例给出可直接运行、可直接套用的完整解题方案。读完本文你将掌握如何用增量式计算替代逐位求和来优化数位和计算理解为何本题只需向右、向下两个方向搜索并能在面试中熟练写出 DFS 与 BFS 两种版本的代码。一、题目背景从机器人的运动范围到衣橱整理LCR 130「衣橱整理」是《图解算法数据结构》leetbook_ioa中的一道高频搜索题其原始形态是剑指 Offer 13「机器人的运动范围」。仓库中两份题解文档相互对应leetbook_ioa/docs/LCR 130. 衣橱整理.md本文主体sword_for_offer/docs/剑指 Offer 13. 机器人的运动范围.md同名姊妹题问题描述家居整理师将待整理衣物划分为m x n的二维矩阵从左上角(0, 0)出发每次可向右或向下移动一格若某格子行索引和列索引的数位之和大于给定目标值cnt则不能进入。求机器人能到达的格子数量。该题与仓库中 LCR 129. 字母迷宫原矩阵中的路径同属搜索 回溯家族但本题不需要回溯——因为目标是统计连通区域大小而非寻找特定路径访问过的格子无需还原。这一点在后文 DFS 实现中体现为标记后不再撤销。本文中的cnt对应仓库原题文档剑指 Offer 13 题解及代码中的k二者含义一致均为数位和上限。二、前置工作一数位之和计算与增量公式2.1 基础数位和计算设一数字x向下取整除法符号//求余符号%则有x % 10得到x的个位数字x // 10令x的十进制数向右移动一位即删除个位数字。通过循环累加即可求得数位和s封装函数如下def sums(x): s 0 while x ! 0: s x % 10 x x // 10 return sint sums(int x) { int s 0; while (x ! 0) { s x % 10; x x / 10; } return s; }int sums(int x) { int s 0; while (x ! 0) { s x % 10; x x / 10; } return s; }2.2 数位和增量公式核心优化由于机器人每次只能移动一格即只能从x运动至x ± 1每次只需计算相邻两数的数位和增量。本题约束1 ≤ n, m ≤ 100坐标最大为 99数位和不超过 18以下公式仅在此范围内成立。设x的数位和为s_xx 1的数位和为s_{x1}当(x 1) % 10 0发生进位时s_{x1} s_x - 8。例如19 → 20数位和由10变为210 - 8 2当(x 1) % 10 ! 0无进位时s_{x1} s_x 1。例如1 → 2数位和由1变为2。用三元表达式写作s_x 1 if (x 1) % 10 else s_x - 8(x 1) % 10 ! 0 ? s_x 1 : s_x - 8;(x 1) % 10 ! 0 ? s_x 1 : s_x - 8;这一技巧使得代码在每次递归/迭代中以O(1)常数时间获得下一个格子的数位和避免了对每个新坐标重新执行while循环求和这是本解性能优秀的关键细节也直接体现在仓库全部六份实现代码中。三、前置工作二可达解分析3.1 解的几何形态等腰直角三角形簇根据增量公式可知数位和每逢进位突变一次个位由 9 进到 0 时数位和骤降 8。因此矩阵中满足数位和约束的解其几何形状形如多个等腰直角三角形每个三角形的直角顶点位于0, 10, 20, ...等数位和突变的矩阵索引处。原文档附有n, m 20、cnt ∈ [6, 19]的系列示意图直观展示了可达解、不可达解、非解随cnt增大的连通性变化可在 leetbook_ioa/docs/LCR 130. 衣橱整理.md 中查看。3.2 可达解与不可达解不可达解三角形内的格子虽然都满足数位和要求但机器人每步只能移动一个单元格而相邻三角形之间不一定连通因此机器人不一定能到达称之为不可达解可达解可实际到达的解本题统计的就是可达解的数量。3.3 关键推论只需向右和向下搜索根据可达解的结构和连通性可以证明机器人仅通过向右和向下移动即可访问所有可达解三角形内部全部连通易证两三角形连通处若某三角形内的解为可达解则必与其左边或上边的三角形连通即相交机器人必可从左边或上边走进此三角形。因此DFS / BFS 中只需要探索下方、右方两个方向无需向四个方向搜索这也避免了向上、向左移动可能产生的重复路径进一步降低了分支因子。仓库中的实现全部遵循这一结论例如 sword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s1.py 中仅递归调用dfs(i 1, j, ...)与dfs(i, j 1, ...)两个方向。四、方法一深度优先遍历DFS深度优先搜索可理解为暴力模拟机器人在矩阵中的所有路径通过递归先朝一个方向搜到底再回溯至上个节点沿另一方向继续搜索。剪枝可行性剪枝搜索中遇到数位和超出目标值、或该元素已被访问立即返回不再深入。4.1 算法解析递归参数当前元素的矩阵行列索引i、j以及两者的数位和si、sj终止条件当 ① 行列索引越界或② 数位和si sj超出目标值cnt或③ 当前元素已访问过时返回0不计入可达解递推工作标记当前单元格将索引(i, j)存入集合visited代表已访问搜索下一单元格计算当前元素下方、右方两元素的数位和开启下层递归回溯返回值返回1 右方搜索的可达解总数 下方搜索的可达解总数即从本单元格出发递归搜索到的可达解总数。4.2 代码实现Java / C 代码中visited为辅助矩阵Python 中为set集合。class Solution: def wardrobeFinishing(self, m: int, n: int, cnt: int) - int: def dfs(i, j, si, sj): if i m or j n or cnt si sj or (i, j) in visited: return 0 visited.add((i, j)) return 1 dfs(i 1, j, si 1 if (i 1) % 10 else si - 8, sj) dfs(i, j 1, si, sj 1 if (j 1) % 10 else sj - 8) visited set() return dfs(0, 0, 0, 0)class Solution { int m, n, cnt; boolean[][] visited; public int wardrobeFinishing(int m, int n, int cnt) { this.m m; this.n n; this.cnt cnt; this.visited new boolean[m][n]; return dfs(0, 0, 0, 0); } public int dfs(int i, int j, int si, int sj) { if (i m || j n || cnt si sj || visited[i][j]) return 0; visited[i][j] true; return 1 dfs(i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj) dfs(i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8); } }class Solution { public: int wardrobeFinishing(int m, int n, int cnt) { vectorvectorbool visited(m, vectorbool(n, 0)); return dfs(0, 0, 0, 0, visited, m, n, cnt); } private: int dfs(int i, int j, int si, int sj, vectorvectorbool visited, int m, int n, int cnt) { if (i m || j n || cnt si sj || visited[i][j]) return 0; visited[i][j] true; return 1 dfs(i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj, visited, m, n, cnt) dfs(i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8, visited, m, n, cnt); } };仓库中可直接运行的同构实现方法名movingCount参数名ksword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s1.pysword_for_offer/codes/java/sfo_13_range_of_motion_of_a_robot_s1/sfo_13_range_of_motion_of_a_robot_s1.javasword_for_offer/codes/cpp/sfo_13_range_of_motion_of_a_robot_s1/sfo_13_range_of_motion_of_a_robot_s1.cpp五、方法二广度优先遍历BFSBFS 与 DFS 目标一致——遍历整个矩阵区别仅在于搜索顺序DFS 朝一个方向走到底再回退BFS 则按平推的方式逐层向外搜索通常借助队列实现。5.1 算法解析初始化将机器人初始点(0, 0)及其数位和(0, 0, 0, 0)加入队列queue迭代终止条件queue为空代表已遍历完所有可达解迭代工作单元格出队弹出队首单元格的索引与数位和作为当前搜索单元格判断是否跳过若 ① 行列索引越界或② 数位和超出目标值cnt或③ 当前元素已访问过执行continue标记当前单元格将索引(i, j)存入集合visited单元格入队将当前元素下方、右方单元格的索引与数位和加入queue返回值集合visited的长度len(visited)即可达解数量。Java / C 使用辅助变量res计数Python 直接返回集合长度。5.2 代码实现class Solution: def wardrobeFinishing(self, m: int, n: int, cnt: int) - int: queue, visited [(0, 0, 0, 0)], set() while queue: i, j, si, sj queue.pop(0) if i m or j n or cnt si sj or (i, j) in visited: continue visited.add((i, j)) queue.append((i 1, j, si 1 if (i 1) % 10 else si - 8, sj)) queue.append((i, j 1, si, sj 1 if (j 1) % 10 else sj - 8)) return len(visited)class Solution { public int wardrobeFinishing(int m, int n, int cnt) { boolean[][] visited new boolean[m][n]; int res 0; Queueint[] queue new LinkedListint[](); queue.add(new int[] { 0, 0, 0, 0 }); while (queue.size() 0) { int[] x queue.poll(); int i x[0], j x[1], si x[2], sj x[3]; if (i m || j n || cnt si sj || visited[i][j]) continue; visited[i][j] true; res; queue.add(new int[] { i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj }); queue.add(new int[] { i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8 }); } return res; } }class Solution { public: int wardrobeFinishing(int m, int n, int cnt) { vectorvectorbool visited(m, vectorbool(n, 0)); int res 0; queuevectorint que; que.push({ 0, 0, 0, 0 }); while (que.size() 0) { vectorint x que.front(); que.pop(); int i x[0], j x[1], si x[2], sj x[3]; if (i m || j n || cnt si sj || visited[i][j]) continue; visited[i][j] true; res; que.push({ i 1, j, (i 1) % 10 ! 0 ? si 1 : si - 8, sj }); que.push({ i, j 1, si, (j 1) % 10 ! 0 ? sj 1 : sj - 8 }); } return res; } };仓库中 BFS 版本的可运行实现sword_for_offer/codes/python/sfo_13_range_of_motion_of_a_robot_s2.pysword_for_offer/codes/java/sfo_13_range_of_motion_of_a_robot_s2/sfo_13_range_of_motion_of_a_robot_s2.javasword_for_offer/codes/cpp/sfo_13_range_of_motion_of_a_robot_s2/sfo_13_range_of_motion_of_a_robot_s2.cpp六、复杂度分析设矩阵行列数分别为M, N时间复杂度 O(MN)最差情况下机器人遍历矩阵中所有单元格每个格子至多被访问一次复杂度为 O(MN)空间复杂度 O(MN)最差情况下visited内存储矩阵所有单元格的索引占用 O(MN) 额外空间。两种方法在最坏情况下的时间、空间复杂度完全一致实际选择取决于面试场景——DFS 代码更短、递归语义直观BFS 则避免了深递归可能带来的系统栈开销。七、仓库源码验证与测试用例仓库为本题提供了完整的解题代码 驱动测试结构可在本地直接编译运行验证Python 实现文件末尾附有# Test Case 与 Driver Code例如 sfo_13_range_of_motion_of_a_robot_s1.py 使用测试用例m 2, n 3, k 1调用slt.movingCount(m, n, k)并打印结果Java 实现main()方法中构造同样的测试用例并System.out.println(res)见 sfo_13_range_of_motion_of_a_robot_s1.javaC 实现main()中以Solution *slt new Solution()调用并cout res见 sfo_13_range_of_motion_of_a_robot_s2.cpp。手动验证测试用例对m 2, n 3, k 1的 2×3 矩阵坐标数位和满足si sj ≤ 1的格子为(0,0)、(0,1)、(1,0)共3个。可见 DFS、BFS 两版代码在该用例下应输出3读者可据此自测以确认理解正确。八、小结LCR 130「衣橱整理」是搜索与剪枝的经典入门题其核心方法论可归纳为三条数位和增量公式以 O(1) 代价获得相邻格子的数位和是性能关键可达性分析借助等腰直角三角形簇的连通性结论把四方向搜索降为仅向右、向下直接减小搜索空间DFS / BFS 双模板DFS 用递归 集合标记BFS 用队列 集合标记二者复杂度相同可随面试场景灵活切换。如需复习同类搜索题可对照阅读 LCR 129. 字母迷宫需回溯还原标记的矩阵路径搜索体会两者在标记是否需要还原上的本质差异仓库中全部题解与代码的组织方式见 README.md。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考