经典BFS走迷宫问题

思想：通过队列实现BFS，尝试每一种路径可能。若当前位置可以走，则把当前位置标志已访问。

import java.util.*;
class Node{
    int x;
    int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Solution {

    public int movingCount(int threshold, int rows, int cols)
    {
        //标志位，表示是否已走过
        int[][]visits = new int[rows][cols];
        //上下左右四个方向
        int[][]dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        Queue<Node>queue = new LinkedList<Node>();
        queue.offer(new Node(0,0));
        visits[0][0] = 1;
        int count = 1;
        if(threshold<0)return 0;
        while(!queue.isEmpty()){
            Node node = queue.poll();
            for(int i=0; i<dir.length; i++){
                int x = node.x + dir[i][0];
                int y = node.y + dir[i][1];
                if(x>=0 && x<rows && y>=0 && y<cols){
                    //当前方向可以走并且x y位数之和小于threshold，入队
                    if(visits[x][y]==0 && check(x,y,threshold)){
                        queue.offer(new Node(x, y));
                        visits[x][y] = 1;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    //判断x y是否位数之和是否小于等于threshold
    public static Boolean check(int x, int y, int threshold){
        int t1 = 0;
        while(x!=0){
            t1 += x%10;
            x/=10;
        }
        int t2 = 0;
        while(y!=0){
            t2 += y%10;
            y/=10;
        }
        if(t1+t2 <= threshold)
            return true;
        return false;
    }
}