JZ13 机器人的运动范围

描述

地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？

数据范围：0 ≤ threshold ≤ 15，1 ≤ rows,cols ≤ 100

进阶：空间复杂度 O(nm)，时间复杂度 O(nm)

示例1

输入：

1,2,3

返回值：

3

复制

示例2

输入：

0,1,3

返回值：

1

示例3

输入：

10,1,100

返回值：

29

说明：

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的      

解析

本题与 JZ12 类似，都是在矩阵中寻找能到达的位置，因此思路是一样的：从某一个格子开始，前往它周围的四个格子，到达新的格子后判断当前位置是否符合要求，不符合则直接返回，符合则继续前往周围的格子。程序的实现方式为递归。

但本题与 JZ12 的寻找一条路径不同，本题的要求是寻找所有能到达的格子。

在 JZ12 中，递归的停止条件是路径字符串为空，说明走到头了；但在本题中，递归不需要特定的停止条件，因为题目的要求，需要前往任何可能到达的位置，而某个位置是否要进行递归由它是否符合规则和是否访问过决定的。若进入某一位置后，它不符合规则或已访问过，就会直接返回，因此这个位置不会产生递归栈，也不会被计入可到达的位置。

总而言之，本题的关键点为：

1. 因为规则和访问标记数组 visited 的限制，“机器人”是不会前往不符合规则的格子和走回头路的，这使得程序在有限地遍历而不是无限地递归。
2. 与求树的深度问题类似，当前格子能到达的格子数，是它周围四个格子所能到达格子的总和加一。

代码清单

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        // 访问记录矩阵，默认 false
        boolean visited[][] = new boolean[rows][cols];
        // 从0,0开始寻找能到达的格子
        // 类似于跳台阶问题，当前的到达的格子数等于四周格子能到达格子数之和
        int count = movingCountCore(threshold,rows,cols,0,0,visited);
        return count;
    }
    
    public int movingCountCore(int threshold,int rows,int cols,
                               int row,int col,boolean[][] visited){
        // 先判断当前格子是否有效
        if(canMove(threshold,rows,cols,row,col,visited)){
            // 将当前格子设置为走过
            visited[row][col] = true;
            // 当前格子能走，则上一个格子能到达的地方为当前格子和当前格子的后续
            int count = 1 + movingCountCore(threshold,rows,cols,row-1,col,visited)
                + movingCountCore(threshold,rows,cols,row+1,col,visited)
                + movingCountCore(threshold,rows,cols,row,col-1,visited)
                + movingCountCore(threshold,rows,cols,row,col+1,visited);
            return count;
        }else{
            // 当前格子走不通
            return 0;
        }
    }
    // 判断能否进入某个格子
    public boolean canMove(int threshold,int rows,int cols,
                               int row,int col,boolean[][] visited){
        // 超出范围，直接返回，必须是大于等于！！！否则还是会越界！！！
        if(row<0 || row>=rows || col<0 || col>=cols)
            return false;
        // 若已走过，不必在走
        if(visited[row][col]==true)
            return false;
        // 不符合进入的规则，也不能走
        if(getDigitalSum(row)+getDigitalSum(col)>threshold)
            return false;
        // 符合所有条件，可以进入
        return true;
    }
    
    // 获取一个数字的数位和
    public int getDigitalSum(int num){
        int sum = 0;
        while(num!=0){
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }
}

虽然有四个方法，但其实总代码量很少且方法各司其职，思路清晰：

1. movingCount：入口方法，从起点开始获取总共能到达的格子数；
2. movingCountCore：核心方法，计算某格子能到达的格子数，即为它周围四个格子能到达格子数加一；
3. canMove：判断方法，根据规则和访问标记数组 visited 判断某格子是否能进入；
4. getDigitalSum：工具方法，计算数位和，为判断方法服务。

总结

本题与 JZ12 类似，都是处理一个矩阵中寻找路线的问题。对这种问题，将矩阵看做数组，寻找路线使用递归方式和回溯法，可以产生比较好的思路。不过我太久没用递归，总是忘记考虑递归的停止条件。