题目描述

blablabla

样例

blablabla

(BFS) $时间复杂度O(n)$

Node类作为点的封装，包含x，y横纵坐标属性。
提供上下左右四个方向的移动方法，用数组move表示。
book数组，0代表没走过，1代表走过。
res表示最终结果。
check方法判断当前点是否满足各位和小于threshold要求。
while循环中提供for循环来进行上下左右四个方向的移动权限判断，能移动的点全部加入队列。
每次while循环从队列抽取元素并判断以该点为起点能移动到的下一个点。
队列为空代表搜索结束，退出循环并输出结果。

Java 代码

class Solution {

    class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int movingCount(int threshold, int rows, int cols)
    {
        if(rows == 0 && cols == 0) return 0;
        int res = 1;
        int[][] move = {{0,1},{1,0},{0,-1},{-1,0}};
        int[][] book = new int[rows][cols];
        book[0][0] = 1;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0,0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = node.x + move[i][0];
                int ny = node.y + move[i][1];

                if(nx >=0 && ny >=0 && nx < rows 
                   && ny < cols && book[nx][ny] == 0 
                   && check(threshold,nx,ny)) {
                    res++;
                    queue.offer(new Node(nx,ny));
                    book[nx][ny] = 1;
                }
            }
        }

        return res;
    }
    static boolean check(int k, int i, int j) {
        int res = 0;
        while(i != 0) {
            res += (i % 10);
            i /= 10;
        }
        while(j != 0) {
            res += (j % 10);
            j /= 10;
        }
        return res <= k;
    }
}