13.机器人的运动范围 #

class Solution {
    // DFS 深度优先遍历
    public int m, n, k;
    public boolean[][] v; // 记录访问过的位置
    public int movingCount(int m, int n, int k) {
        if(k == 0) return 1;
        // 初始化
        this.m = m;
        this.n = n;
        this.k = k;
        this.v = new boolean[m][n];
        for(boolean[] arr : this.v){
            Arrays.fill(arr, false);
        }
        // 从[0,0]开始遍历
        return dfs(0,0);
    }
    public int dfs(int i, int j){
        // 边界情况以及不符合情况
        if(i < 0 || j < 0 || i >= m || j >= n || singleSum(i) + singleSum(j) > k || v[i][j]) return 0;
        // 修改标记
        v[i][j] = true;
        // 1代表该点，继续向右和向下寻找更多的点
        return 1 + dfs(i+1,j) + dfs(i,j+1);
    }
    // 计算一个数各个位上数值的和
    public int singleSum(int num){
        if(num < 10) return num;
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}


class Solution {
    // BFS 广度优先遍历
    public int movingCount(int m, int n, int k) {
        if(k == 0) return 1;
        // 记录访问过的位置
        boolean[][] v = new boolean[m][n];
        // 初始化
        for(boolean[] arr : v){
            Arrays.fill(arr, false);
        }
        // 记录走过的点
        Queue<int[]> q = new LinkedList<int[]>();
        // 添加[0,0]点
        q.offer(new int[]{0,0});
        int ans = 1;
        v[0][0] = true;
        // 开始前进
        while(!q.isEmpty()){
            // 取出一个点，记录x，y坐标
            int[] pos =  q.poll();
            int i = pos[0], j = pos[1];
            // 向右，向下前进
            for(int o = 0; o < 2;o++){
                // 记得加括号
                int ii = i + (o == 0 ? 0 : 1);
                int jj = j + (o == 0 ? 1 : 0);
                // 判断下一个点是否可行
                if(ii < 0 || jj < 0 || ii >= m || jj >= n || v[ii][jj] || singleSum(ii) + singleSum(jj) > k) continue;
                // 可行，则将点加入队列
                q.offer(new int[]{ii,jj});
                v[ii][jj] = true;
                ans++;
            }
        }
        return ans;
    }
    // 计算一个数各个位上数值的和
    public int singleSum(int num){
        if(num < 10) return num;
        int sum = 0;
        while(num > 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}