回溯法 / BFS
打个卡

回溯

class Solution {
    private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, 1, -1};
    private boolean[][] visited;
    private boolean[][] counted;
    private int cnt;
    public int movingCount(int threshold, int rows, int cols) {
        if(rows == 0 || cols == 0)return 0;
        visited = new boolean[rows][cols];
        counted = new boolean[rows][cols];
        visited[0][0] = true;
        counted[0][0] = true;
        cnt ++;
        dfs(0, 0, threshold, rows, cols);

        return cnt;
    }

    private void dfs(int x, int y, int threshold, int rows, int cols){
        int x_ = x, y_ = y;
        int sum = 0;
        while(x_ > 0 || y_ > 0){
            sum = sum + x_ % 10;
            sum = sum + y_ % 10;
            x_ /= 10;
            y_ /= 10;
        }
        if(sum > threshold)return;
        if(sum > 0 && counted[x][y])return;
        if(!counted[x][y]){
            counted[x][y] = true;
            cnt ++;
        }
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(a >=0 && a < rows && b >= 0 && b < cols && !visited[a][b]){
                visited[a][b] = true;
                dfs(a, b, threshold, rows, cols);
                visited[a][b] = false;
            }
        }
    }
}

要剪枝，不然 TLE

BFS

class Solution {
    private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, 1, -1};
    private boolean[][] visited;
    public int movingCount(int threshold, int rows, int cols)
    {
        if(rows <= 0 || cols <= 0 || threshold < 0)return 0;
        Deque<Pair> queue = new LinkedList<>();
        int count = 0;
        visited = new boolean[rows][cols];
        for(int i = 0; i < rows; i ++)
            for(int j = 0; j < cols; j ++)
                visited[i][j] = false;
        queue.offer(new Pair(0 ,0));
        count ++;
        visited[0][0] = true;
        while(!queue.isEmpty()){
            Pair p = queue.poll();
            for(int i = 0; i < 4; i ++){
                int x = p.first + dx[i], y = p.second + dy[i];
                if(x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y] && canReach(x, y, threshold)){
                    queue.offer(new Pair(x, y));
                    visited[x][y] = true;
                    count ++;
                }
            }
        }

        return count;
    }

    private boolean canReach(int x, int y, int threshold){
        int sum = 0;
        while(x > 0 || y > 0){
            sum += x % 10 + y % 10;
            x /= 10;
            y /= 10;
        }

        return sum <= threshold;
    } 

    private class Pair {
        int first;
        int second;

        Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }
}