JZ66 机器人的运动范围

3.bfs 队列
初始化方式
new int[]{i, j + 1}

import java.util.*;
public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        //临时变量visited记录格子是否被访问过
        boolean[][] visited = new boolean[rows][cols];
        int res = 0;
        //创建一个队列，保存的是访问到的格子坐标，是个二维数组
        Queue<int[]> queue = new LinkedList<>();
        //从左上角坐标[0,0]点开始访问，add方法表示把坐标
        // 点加入到队列的队尾
        queue.add(new int[]{0, 0});
        while (queue.size() > 0) {
            //这里的poll()函数表示的是移除队列头部元素，因为队列
            // 是先进先出，从尾部添加，从头部移除
            int[] x = queue.poll();
            int i = x[0], j = x[1];
            //i >= m || j >= n是边界条件的判断，k < sum(i, j)判断当前格子坐标是否
            // 满足条件，visited[i][j]判断这个格子是否被访问过
            if (i >= rows || j >= cols || threshold < check(i, j) || visited[i][j])
                continue;
            //标注这个格子被访问过
            visited[i][j] = true;
            res++;
            //把当前格子下边格子的坐标加入到队列中
            queue.add(new int[]{i + 1, j});
            //把当前格子右边格子的坐标加入到队列中
            queue.add(new int[]{i, j + 1});
        }
        return res;
    }

    public int check(int row, int col){
        int sum = 0;
        while(row != 0){
            sum = sum + (row % 10);
            row = row / 10;
        }
        while(col != 0){
            sum = sum + (col % 10);
            col = col / 10;
        }
        return sum;
    }

}

1.dfs

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] visited = new boolean[rows][cols];
        int sum = dfs(0,0,rows,cols,threshold,visited);
        return sum;
    }

    public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        //i >= m || j >= n是边界条件的判断，k < sum(i, j)判断当前格子坐标是否
        // 满足条件，visited[i][j]判断这个格子是否被访问过
        if (i >= m || j >= n || k < check(i, j) || visited[i][j])
            return 0;
        //标注这个格子被访问过
        visited[i][j] = true;
        //沿着当前格子的右边和下边继续访问
        return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
    }

    public int check(int row, int col){
        int sum = 0;
        while(row != 0){
            sum = sum + (row % 10);
            row = row / 10;
        }
        while(col != 0){
            sum = sum + (col % 10);
            col = col / 10;
        }
        return sum;
    }

}

2.DP 思路 往下寻找
o(n^2)

通过dfs或者bfs 能节省点时间

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        int[][] dp = new int[rows+1][cols+1];
        int sum = 0;
        //多一行初始化
        dp[0][0] = 1;
        dp[0][1] = 1;
        dp[1][0] = 1;

        for(int i=1; i<=rows;i++){
            for(int j =1; j <= cols ; j++){
            //多一行初始化 数会变 因此 check 需要-1
                if(i>=0 && j>=0 && check(i-1,j-1) <= threshold){
                    if(dp[i][j-1] == 1 || dp[i-1][j] == 1) {
                        dp[i][j] = 1;
                        sum++;}
                }
            }
        }
        return sum;
    }
    public int check(int row, int col){
        int sum = 0;
        while(row != 0){
            sum = sum + (row % 10);
            row = row / 10;
        }
        while(col != 0){
            sum = sum + (col % 10);
            col = col / 10;
        }
        return sum;
    }

}