力扣 - 剑指 Offer 13. 机器人的运动范围

题目

剑指 Offer 13. 机器人的运动范围

思路1（DFS）

• 通过DFS递归，先往一个方向递归到最深地方，然后回溯，直到吧所有的条件都访问一遍
• 我们使用visited数组记录在访问过程中被访问的位置（因为每个位置最多只能访问一次）
• 然后每次递归都要判断是否满足如下条件：
  1. 不超边界，始终坐标位置保证在范围内
  2. 通过visited判断是否被访问过
  3. 判断各个位数之和是否大于k
  4. 如果以上条件满足其一，则结束递归（不能继续往下走了，没路可走。。）
• 如果遍历到头，条件不满足，就返回0
• 然后回溯的时候带上个递归的值加上当前的1(1是因为当前访问了一次，如果没有访问到，就会直接返回0)，向上传递，累加起来，即为总的可到达的格子数

代码

class Solution {

    // 将m、n、k定义为全局变量
    int m, n, k;
    // 标记访问过的位置
    boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        // 初始化数组，元素全部为false，访问过的记为true
        visited = new boolean[m][n];
        // 开始搜索
        int res = dfs(0, 0);

        return res;
    }

    public int dfs(int i, int j) {
        // 1. 判断边界
        // 2. 判断是否被访问过了
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
            return 0;
        }

        // 判断是否超过k
        if (help(i, j)) {
            return 0;
        }

        // 符合条件的做个标记，只能统计一次，再次访问就无效了
        visited[i][j] = true;
        
        // 能访问到这里说明已经确认访问到了一次了，因此在递归结束回溯的时候要加上当前的1作为返回值得以累加
        // 然后递归四个方向
        int res = 1 + dfs(i + 1, j) +
                      dfs(i - 1, j) +
                      dfs(i, j + 1) +
                      dfs(i, j - 1);

        return res;
    }

    // 判断坐标各位之和是否超过k
    public boolean help(int i, int j) {
        int count = 0;
        while (i != 0) {
            count += i % 10;
            i /= 10;
        }
        while (j != 0) {
            count += j % 10;
            j /= 10;
        }
        return count > k;
    }
}

复杂度分析

• 时间复杂度：\(O(MN)\)，M为行数。N为列数，最坏情况下要遍历全部，即MN
• 空间复杂度：\(O(MN)\)，visited记录访问过的数组，占MN的空间

思路2（BFS）

• 本题也可以使用BFS解决，和DFS有所不同的是：
  • DFS是先往一个方向递归到底部在回溯递归另一条路径到底部，直到全部遍历；
  • 而BFS是一层一层遍历的（层序遍历），使用队列存储，遍历流程如下：将队列的队头元素出队，然后进行必要计算操作，最后将这个元素的第一层子元素加入到队列末尾（本题是将下方和右方的子元素入队），都让，如果子元素不满足某些条件（本题有一些条件限制），就不入队。。。然后重复执行，直到队列为空，说明遍历结束
• 和上一题一样，也需要使用visited标记访问过的元素

代码

class Solution {

    public int movingCount(int m, int n, int k) {
        int count = 0;
        boolean[][] visited = new boolean[m][n];
        Deque queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            // 从队列中取出一个
            int[] cur = queue.poll();
            // 获取两个坐标值
            int i = cur[0];
            int j = cur[1];

            // 判断边界
            // 判断是否访问过
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) {
                continue;
            }
            // 判断是否小于等于k
            if (help(i, j, k)) {
                continue;
            }

            // 标记访问过
            visited[i][j] = true;
            // 访问次数加1
            count++;
            
            // 将当前元素的下方和右方添加到队列中
            queue.offer(new int[]{i+1, j});
            queue.offer(new int[]{i, j+1});
        }

        return count;
    }

    // 判断坐标各位之和是否超过k
    public boolean help(int i, int j, int k) {
        int count = 0;
        while (i != 0) {
            count += i % 10;
            i /= 10;
        }
        while (j != 0) {
            count += j % 10;
            j /= 10;
        }
        return count > k;
    }
}

复杂度分析

• 时间复杂度：\(O(MN)\)，M为行数。N为列数，最坏情况下要遍历全部，即MN
• 空间复杂度：\(O(MN)\)，最坏情况下，队列中存储矩阵所有单元格索引，需要\(O(MN)\)的空间