剑指 Offer 系列面试题 13. 机器人的运动范围

大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。

今天分享的题目来源于剑指 Offer 系列 面试题 13. 机器人的运动范围。

题目汇总链接：https://www.algomooc.com/hi-offer

一、题目描述

地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标[0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格[35, 37]，因为 3 + 5 + 3 + 7 = 18 。但它不能进入方格 [35, 38]，因为 3 + 5 + 3 + 8 = 19。

请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

• 1 <= n,m <= 100
• 0 <= k <= 20

二、题目解析

我们依旧用 四步分析法 进行结构化的分析，帮助我们思考和发现规律，写出合理的代码。

• 模拟：模拟题目的运行。
• 规律：尝试总结出题目的一般规律和特点。
• 匹配：找到符合这些特点的数据结构与算法。
• 边界：考虑特殊情况。

1、模拟

我们需要统计能走多少个格子，不能少统计也不能重复统计。

• 避免少统计：遍历所有能移动的格子
• 避免重复统计：每次统计完一个格子，将其移除

由于机器人是从左上角(0,0) 开始移动，所以移动方向必然是 下方 或者 右方，即机器人从格子的 左方 或者 上方 进入格子，从格子的 下方 或者 右方 离开格子。

接下来依次观察一下随着 k 的变大，符合要求的区域是哪些。

注：符合要求的区域并不代表机器人一定能够到达，因为中间有一些不符合要求的区域，机器人无法跨越。

当 k = 0 时:

当 k = 1 时:

当 k = 2 时:

当 k = 3 时:

当 k = 4 时:

我们以 k = 4 为例，演示机器人的移动。

当机器人移动到 4 这个格子的时候，无法再向下移动，因为下方的 5 超过了 4，属于无法进入的区域，根据我们之前的结论，机器人需要向右移动，此时右方的 5 也超过了 4，机器人无法再移动到任何一个新的格子，需要返回，左方是边界，因此只能向上返回，在返回的同时需要携带统计到的格子，避免遗失。

为了方便演示，在每个格子的四周分别设置一个小方块，表示机器人由此格子出发可到达区域的数量，实际上，我们只需要观察格子的下方和右方统计数即可，因为机器人只能此格子的 下方 或者 右方 离开格子，返回时也必然从此格子的 下方 或者 右方 返回到此格子并带来了统计的数量。

机器人从 4 返回 3 的同时，携带着统计的数量 1，记录在格子 3 的下方，表明机器人由 3 这个格子出发可到达区域的数量为 1，同时，为了避免多次统计格子 4，将格子 4 的状态清除。

接下来，让机器人从格子 3 的右方开始出发，探索右方可到达的区域。

到达格子 4 后，下方和右方都不可到达，返回并携带数量，同时清除状态。

接下来，机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作。

最终统计出，当 k = 4 的时候，机器人可移动到达的格子数量为 15 。

2、规律

在搜索过程中，如果下方格子与右方格子不符合要求，则向上或者向左返回上一个格子

3、匹配

机器人先从一个方向出发，直到到达不可到达的区域时才返回，符合 深度优先遍历 的性质。

机器人不断的重复从一个格子出发探索、返回携带数量、清除区域的操作，符合 递归 的性质。

所以，我们可以使用一个数组用来记录符合要求的格子是否被机器人访问过，若没有访问过，则在机器人返回的过程中将结果 + 1。

具体操作如下：（参考自 Krahets ）

• 递归参数： 当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 sumi, sumj 。
• 终止条件：
  • ① 行列索引越界
  
  
  • ② 数位和超出目标值 k ，即不满足行坐标和列坐标的数位之和小于 k 的格子

• ③ 已经被访问过的重复格子
  
• 递推工作：
  
  • 标记当前单元格 ：将索引 (i, j) 存入临时变量 visited 中，代表此单元格已被访问过。
  
  
• 搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
  
• 回溯返回值： 返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
  

4、边界

• 超出边界的格子
• 已经被访问过的重复格子
• 不满足行坐标和列坐标的数位之和小于 k 的格子

三、动画描述

四、图片描述

五、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int movingCount(int m, int n, int k) {
     // 使用临时变量 visited 记录格子是否被访问过
     boolean[][] visited = new boolean[m][n];
     // 开始深度优先遍历
     return dfs(0, 0, m, n, k, visited);
    }

    public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
         // 行列索引越界 
        if( i >= m || j >= n ) return 0;

        // 数位和超出目标值 k ，即不满足行坐标和列坐标的数位之和小于 k 的格子
        if( k < sum( i , j ) ) return 0;

         // 已经被访问过的重复格子
        if ( visited[i][j] ) return 0;

         //机器人进入了一个新格子，标注这个格子被访问过
         visited[i][j] = true;

        //沿着当前格子的右边和下边继续访问
        return 1 + dfs( i + 1, j , m ,  n , k , visited ) + dfs( i , j + 1, m , n , k , visited);

    }

    //计算两个坐标数字的和
    private int sum(int i, int j) {
        int sum = 0;

        while (i != 0) {
             // 通过求余和取整的操作来计算
             sum += i % 10;
             i /= 10;
         }
        while (j != 0) {
            sum += j % 10;
             j /= 10;
          }
        return sum;
    }
}

六、复杂度分析

时间复杂度

时间复杂度：O(m * n)

空间复杂度

空间复杂度：O(m * n)

七、相关标签

• 深度优先搜索
• 递归
• 数组
• 回溯

八、参考链接

• https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/
• https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
• https://www.algomooc.com/263.html