java图的遍历-机器人的活动范围

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

解题纪要-参考官方题解

该题不会做，需要复习。需要实现图的深度遍历和广度遍历

Java代码实现-具体见注释

//图的深度遍历
/*public class Solution1 {
    int[] dir=new int[]{-1,0,1,0,-1};//左上右下的顺序走
    int ans=0;

    public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold <= 0) return 0;
        int[][] mark=new int[rows][cols];
        dfs(0,0,threshold,rows,cols,mark);
        return ans;
    }
    public int check(int x){
        int sum = 0;
        while(x > 0){
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    public void dfs(int x,int y,int sho,int r,int c,int[][] mark){
        if(x < 0 || x >= r || y < 0 || y >= c || mark[x][y]==1) return;
        if(check(x)+check(y) > sho) return;
        mark[x][y]=1;
        ans += 1;
        for(int i = 0;i < 4;i++){
            dfs(x + dir[i],y + dir[i + 1],sho,r,c,mark);
        }
    }
}*/
//图的广度遍历
import java.util.*;
public class Solution{
    int[] dir=new int[]{-1,0,1,0,-1};//左上右下的顺序走
    public int check(int x){
        int sum = 0;
        while(x > 0){
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    public int movingCount(int threshold, int rows, int cols)
    {
        if(threshold <= 0) return 0;
        //新建一个二维数组标记走过的路
        boolean[][] mark = new boolean[rows][cols];
        //创建一个变量保存走过的格子树
        int res = 0;
        //建一个队列，里面存储一个4个元素的数组
        //[0,0] 行和列的值
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        mark[0][0]=true;
        //将可能符合的坐标放入队列中，当队列为空时退出循环
        while(!queue.isEmpty()){
            int[] tem = queue.poll();
            res++;
            for(int i=0;i<4;i++){
                int x=tem[0]+dir[i],y=tem[1]+dir[i+1];
                if(x >= 0 && x < rows && y >= 0 && y < cols && mark[x][y] == false){
                    if(check(x)+ check(y) <= threshold){
                        queue.add(new int[]{x,y});
                        mark[x][y] = true;
                    }
                }
            }
        }
        return res;
    }
}