剑指offer—机器人的运动范围 解答

剑指offer—机器人的运动范围

题目描述

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

思路

这题是一道遍历的题目,我们可以使用dfs、bfs和递归,这里选用较少人用的bfs,使用队列实现,我们对每一个点都有四种走法,我们只需要把四种走法都放入队列就好了,知道队列为空

  • 难点1:队列存储点

    我们无法把一个二维数组的存储在一个队列中(不创建对象),我们只能把数组转换为一维数组去存储,存储每一个元素的位置(所在列+所在行*总的列数),这样就可以存储每一个元素,并且可以通过除法和取余操作获得横坐标和纵坐标

    int row = num/n ;
    int col = num%n ;
  • 难点2:根据一个数获取它的数位之和

    public int getNumbit(int num){
            int sum=0;
            int temp=num;
            while(temp!=0){
                sum+=temp%10;
                temp/=10;
            }
            return sum;
        }
  • 难点3:判重

    需要维护一个一维boolean数组(数组最长和m*n)根据队列中存储的点的位置判断该点是否被访问过,如果被访问过不需要进行累加,直接继续下一次,在每一次访问过后把该点数组值设置为true,代表已经被访问

代码

import java.util.Queue;
import java.util.LinkedList;
public class Solution {
    public int movingCount(int k, int m, int n){
        if(k<=0||m<=0||n<=0) return 0;
        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        boolean []readed = new boolean [m*n];
        q.add(0);
        while(!q.isEmpty()){
            int num = q.poll();
            System.out.println("出队:"+num);
            if(readed[num]) {
               continue; 
            }
            count++;
            readed[num] = true;
            int []dx = new int[]{0,0,-1,1};int []dy = new int[]{1,-1,0,0};
            for(int i=0;i<4;i++){
                int row = num/n  + dx[i];
                int col = num%n + dy[i];
                if(row>=0&&col>=0&&row<m&&col<n&&getNumbit(row)+getNumbit(col)<=k){
                    q.add(row*n+col);
                }
            }
        }
        return count;
    }
    public int getNumbit(int num){
        int sum=0;
        int temp=num;
        while(temp!=0){
            sum+=temp%10;
            temp/=10;
        }
        return sum;
    }
}