《剑指offer》第13题机器人的运动范围

机器人的运动范围

https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8?tpId=13&&tqId=11219&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

Java

题目描述

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

解题思路

思路一：回溯
首先在某个节点处，要调用递归来决定某个位置的下一步去哪，此时有4个选择，每个选择都会进入下一个递归调用。当进入某个位置时，应当标记这个位置已访问过，避免之后又来到这里，从而重复计算，因此设计一个boolean的数组，这里设计的二维，也可以通过压缩，使用一维数组来表征某个位置是否访问。二维就是记录横纵坐标即第i行第j列的数据被访问了，直观，推荐新手用二维。接着就是边界条件和递归结束的条件的判断了。
这类型题也是有套路的，主方法在原点作为起点，调用第一次递归后，在递归方法中，首先判断边界条件以及题目中所提的要求是否满足（本题的要求就是cal方法中的实现），都没问题，说明该位置可以访问，然后改变对应位置的标记。然后就是以该节点为中心，考虑下一步怎么走，本题就是4种走法，可以分开写，也可以一起写，由于本题是计数，所以就直接加在一起。然后return这些求和结果再+1，求和结果是下一步走的结果，而+1是本次访问此时的节点的次数。
代码如下：

public class Solution {
    public int movingCount(int threshold, int rows, int cols){
        if(rows <=0 || cols <=0 || threshold <0)
            return 0;
        boolean[][] isVisited = new boolean[rows][cols];
        int count = movingCountCore(threshold,rows,cols,0,0,isVisited);
        return count;
    }
    private int movingCountCore(int threshold,int rows,int cols,
                            int row,int col,boolean[][] isVisited){
        if(row<0 || col<0 || row>=rows || col >= cols || isVisited[row][col] 
           || cal(row)+cal(col) > threshold)
            return 0;
        isVisited[row][col]=true;
        int tem1=movingCountCore(threshold,rows,cols,row-1,col,isVisited);
        int tem2=movingCountCore(threshold,rows,cols,row+1,col,isVisited);
        int tem3=movingCountCore(threshold,rows,cols,row,col-1,isVisited);
        int tem4=movingCountCore(threshold,rows,cols,row,col+1,isVisited);
        return 1+tem1+tem2+tem3+tem4;
    }
    private int cal(int num){
        int sum=0;
        while(num>0){
            sum+=num%10;
            num/=10;
        }
        return sum;
    }
}

另一个版本：广度搜索

代码如下：

import java.util.*;
public class Solution {
    private final int dx[]={-1,1,0,0};
    private final int dy[]={0,0,-1,1};
    public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold <=0 || rows<=0 || cols<=0)
            return 0;
        int ans=0;
        boolean[][] isVisited = new boolean[rows+1][cols+1];
        Queue<Path> queue=new LinkedList<>();
        queue.add(new Path(0,0));
        isVisited[0][0]=true;
        while(!queue.isEmpty()){
            Path p=queue.poll();
            int x=p.getX();
            int y=p.getY();
            for(int i=0;i<4;i++){
                int xx=x+dx[i];
                int yy=y+dy[i];
                if(xx>=0 && xx<rows && yy>=0 && yy<cols && !isVisited[xx][yy] && (cal(xx)+cal(yy)<=threshold)){
                    ans++;
                    isVisited[xx][yy]=true;
                    queue.add(new Path(xx,yy));
                }
            }
        }
        return 0;
    }
    public int cal(int x){
        int sum=0;
        while(x>0){
            sum+=x%10;
            x/=10;
        }
        return sum;
    }
}
class Path{
    private int x;
    private int y;
    public Path(int x,int y){
        this.x=x;
        this.y=y;
    }
    public int getX(){
       return x;
    }
    public void setx(){
        this.x=x;
    }
    public int getY(){
        return y;
    }
    public void setY(){
        this.y=y;
    }
}