机器人的运动范围

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

1. 使用BFS模板
   提供最短路径中的BFS模板如下，对于不同的题目需要进行相应的变化，此题目只用计数就行：

   /**
   * Return the length of the shortest path between root and target node.
   */
   int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
   }

2. 注意终止条件以及能进入队列的条件，当路被挡住时，便不能再加入队列进行判断

3. 坐标从（0,0）开始，可以只走右边和下边就能实现遍历

4. MMP，我怎么这么笨，IDEA里面调试了好久才搞对😤😤😤

   import java.util.Queue;
   import java.util.LinkedList;
   class position{
    int x;
    int y;
    public position(int x,int y){
        this.x=x;
        this.y=y;
    }
    public int getX(){
        return x;
    }
    public int getY(){
        return y;
    }
   }
   public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        Queue<position> que=new LinkedList<>();
        que.add(new position(0,0));
        boolean[][] aq=new boolean[rows+1][cols+1];
        aq[0][0]=true;
        int num=0;
        while(!que.isEmpty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                position po=que.poll();
                if(po.getX()<rows&&po.getY()<cols&&((byteSum(po.getX())+byteSum(po.getY()))<=threshold)){
                    num++;
                    position po1=new position(po.getX()+1,po.getY());
                    position po2=new position(po.getX(),po.getY()+1);
                    if(po1.getX()<rows&&po1.getY()<cols&&aq[po1.getX()][po1.getY()]==false){
                        aq[po1.getX()][po1.getY()]=true;
                        que.add(po1);
                    }
                    if(po2.getX()<rows&&po2.getY()<cols&&aq[po2.getX()][po2.getY()]==false){
                        aq[po2.getX()][po2.getY()]=true;
                        que.add(po2);
                    }
                }
   
            }
   
        }
        return num;
    }
    private int byteSum(int n){
        int sum=0;
        while(n!=0){
            sum=sum+n%10;
            n=n/10;
        }
        return sum;
    }
   }