剑指 Offer 13: 机器人的运动范围

[songyy5517]

地上有一个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

分析 这道题的本质是矩阵中的路径搜索问题。因此，一个很直接的想法就是DFS + 回溯。从坐标 (0, 0) 出发，按照顺时针方向依次搜索矩阵，遇到不合格的坐标则剪枝 & 回溯，考虑下一种情况。

[songyy5517]

思路：深度优先搜索（DFS）

1. 异常处理；
2. 定义全局变量：res记录合格的坐标数，boolean[][] visited记录坐标的访问情况；
3. 定义递归方法dfs，判断当前坐标(r, c)是否合格： （1）递归出口：若坐标越界，则直接返回； （2）将当前坐标置为已访问； （3）计算当前坐标的数位之和，并与threshold进行比较：
   • 若小于等于threshold，则res加1，且按顺时针的相邻坐标递归调用该方法；
   • 若大于threshold，则直接返回。
4. 在主函数中调用dfs方法，最后返回res变量。

复杂度分析

• 时间复杂度： $O(N M)$ 最坏情况下需要遍历所有格子，使用 $O(NM)$ 大小的时间；
• 空间复杂度： $O(N M)$ ，额外定义了 $NM$ 大小的访问数组。

[songyy5517]

import java.util.*;
public class Solution {
    int res = 0;

    public int movingCount(int threshold, int rows, int cols) {
        // 思路：矩阵中的路径搜索问题，可以用回溯法。
        // 1. 异常处理
        if (rows <= 0 || cols <= 0)
            return 0;

        // 2. 定义访问矩阵
        boolean[][] visited = new boolean[rows][cols];

        searchPath(0, 0, threshold, rows, cols, visited);

        return res;
    }

    void searchPath(int r, int c, int threshold, int rows, int cols, boolean[][] visited){
        // 1. 递归出口: 越界，已访问，数位和大于threshold（剪枝）
        if (r < 0 || r >= rows || c < 0 || c >= cols || visited[r][c] == true || digitSum(r, c) > threshold)
            return ;

        res ++;
        visited[r][c] = true;

        searchPath(r + 1, c, threshold, rows, cols, visited);
        searchPath(r - 1, c, threshold, rows, cols, visited);
        searchPath(r, c + 1, threshold, rows, cols, visited);
        searchPath(r, c - 1, threshold, rows, cols, visited);

        return ;
    }

    int digitSum(int r, int c){
        int sum = 0;
        while (r != 0){
            sum += r % 10;
            r /= 10;
        }

        while (c != 0){
            sum += c % 10;
            c /= 10;
        }

        return sum;
    }
}

[songyy5517]

2023/1/17

1. 递归方法中num的作用/用法

2024/3/26

1. visied[r][c] = true; 拿出来解决了无限递归的问题
2. 为什么没有继续递归下去？ 在计算数位之和的过程中： r /= 10; // 改变了r/c的值

2024/4/2

1. 不要忘了访问数组

2024/4/17