JZ13 机器人的运动范围

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

上一篇:数组3


下一篇:用C语言做一个小游戏——扫雷