BFS

思路:使用一个队列 Queue 来维护DFS的访问顺序, 从 (0, 0) 点开始，每次上下左右四个方向继续进行搜索即可
搜索需要满足的条件：

1. 当前结点没有遍历过
2. 当前结点不能出边界
3. 横纵坐标的各位数字之和小于阈值；

class Solution {

    //保存结点信息
    class Node{
        int x = 0;
        int y = 0;

        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int movingCount(int threshold, int rows, int cols)
    {
        return bfs(threshold, rows, cols);
    }

    public int bfs(int threshold, int rows, int cols){
        Queue<Node> queue = new LinkedList();
        queue.offer(new Node(0,0));
        int[] r = new int[]{1,0,-1,0};
        int[] c = new int[]{0,1,0,-1};
        int[][] visit = new int[rows][cols];
        int count = 0;

        //如果阈值为0则直接返回1即可
        if(threshold == 0){
            return 1;
        }

        while(!queue.isEmpty()){
            //每次拿出队列的头部进行搜索
            Node curHead = queue.poll();
            if(curHead.x == rows - 1 && curHead.y == cols - 1){
                break;
            }

            for(int i=0; i<4; i++){
                //计算新节点位置
                int newx = curHead.x + r[i];
                int newy = curHead.y + c[i];

                //当新节点位置合法并且横纵坐标和小于阈值且没被访问过时进行计数
                if(newx >= 0 && newx < rows && newy >= 0 && newy < cols && (calcu(newx) + calcu(newy) <= threshold) && visit[newx][newy] == 0){
                    visit[newx][newy] = 1;
                    count++;
                    queue.offer(new Node(newx, newy));
                }
            }
        }

        return count;
    }

    //计算横纵坐标之和
    public int calcu(int x){
        int res = 0;
        while(x > 0){
            res += x % 10;
            x /= 10;
        }

        return res;
    }
}