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

约 6 分钟
文章信息 11 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 剑指 Offer 剑指 Offer（第 2 版） 微软 美团 百度 快手
标签
动态规划 深度优先搜索 广度优先搜索

题目描述

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

image-20261001225553737

题意分析

机器人从网格左上角 (0, 0) 出发，每次可以向上、下、左、右移动一格，不能越界，也不能进入行坐标数位和加列坐标数位和大于 k 的格子。返回机器人实际能够到达的不同格子数量。

“这个格子允许进入”与“能从起点走到这里”是两件事。合法格子之间可能被不允许进入的区域隔开，不能简单遍历所有坐标并统计数位和合格的数量，需要从起点沿合法路径搜索可达区域。

解法：广度优先搜索可达格子

核心思路

[!blue]

把每个合法格子看作图中的一个节点，上下左右相邻且合法的两个格子之间有边。使用 BFS，从起点逐步扩展；队列中的每个格子都已经找到了一条从起点出发的合法路径。

取出一个可达格子后，依次检查它的四个邻居。先确认行列下标没有越界，才能读取访问表；已经访问过的格子跳过，再对未访问候选检查行列各自的数位和。只有全部条件满足才加入队列，因此搜索不会跨越非法区域。

新格子必须在入队之前立刻标记为已访问。否则两个相邻的已知格子可能在它尚未出队时同时把它加入，导致重复统计。标记后，每个位置最多入队一次，出队时给答案加一即可。

从起点可达的任意合法格子，都存在一条由四方向相邻合法位置组成的路径，BFS 会逐步沿路径把它发现，因此不会漏掉。反过来，只有从已可达格子扩展出的合法邻居才会入队，所以也不会把隔离的合法格子误算进来。

数位和通过反复取个位、去掉个位计算，坐标为零时结果自然是零。要分别计算行、列的数位和再相加，不能改成对坐标和求数位和；坐标增加时数位和也不一定增加，不能用简单的行列范围代替逐点判定。

解题步骤

  1. 创建访问表和队列，将合法起点标记并入队，答案从零开始。
  2. 取出队首，计入一个已到达格子。
  3. 枚举四个邻居，先检查边界，再跳过已访问位置。
  4. 检查 digitSum(row) + digitSum(col) <= k，合格后立即标记并入队。
  5. 队列为空时，起点所在可达区域已经全部处理，返回计数。

代码实现

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        // 每个格子最多入队一次，行数乘列数的容量足够。
        int[][] queue = new int[m * n][2];
        int head = 0;
        int tail = 0;
        int ans = 0;
        int[][] dirs = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1},
        };

        if (digitSum(0) + digitSum(0) > k) {
            return 0;
        }

        visited[0][0] = true;
        queue[tail++] = new int[] {
            0,
            0
        };

        while (head < tail) {
            int[] cell = queue[head++];

            ans++;

            // 只有真正可达且合法的格子才入队，避免重复计数。
            for (int[] dir : dirs) {
                int row = cell[0] + dir[0];
                int col = cell[1] + dir[1];

                // 先检查边界再读取访问数组，避免越界访问。
                if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col]) {
                    continue;
                }

                // 只有当前位置合法还不够，还必须由已经可达的邻居扩展。
                if (digitSum(row) + digitSum(col) > k) {
                    continue;
                }

                // 入队前标记，同一个格子只进入队列一次。
                visited[row][col] = true;
                queue[tail++] = new int[] {
                    row,
                    col
                };
            }
        }

        return ans;
    }

    private int digitSum(int num) {
        int sum = 0;

        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }

        return sum;
    }
}

func movingCount(m int, n int, k int) int {
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }

    dirs := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }
    queue := [][]int{
        {0, 0},
    }
    visited[0][0] = true
    ans := 0

    for head := 0; head < len(queue); head++ {
        cell := queue[head]
        ans++

        // 只有真正可达且合法的格子才入队，避免重复计数。
        for _, dir := range dirs {
            row := cell[0] + dir[0]
            col := cell[1] + dir[1]
            // 先检查边界再读取访问数组，避免越界访问。
            if row < 0 || row >= m || col < 0 || col >= n || visited[row][col] {
                continue
            }
            // 只有当前位置合法还不够，还必须由已经可达的邻居扩展。
            if digitSum(row)+digitSum(col) > k {
                continue
            }
            // 入队前标记，同一个格子只进入队列一次。
            visited[row][col] = true
            queue = append(queue, []int{
                row,
                col,
            })
        }
    }

    return ans
}

func digitSum(num int) int {
    sum := 0
    for num > 0 {
        sum += num % 10
        num /= 10
    }
    return sum
}

复杂度分析

  • 时间复杂度：$O(mn\log(\max(m,n)+1))$，包含数位和计算；题目固定的小坐标范围下，每次计算有常数上界。
  • 空间复杂度：$O(mn)$，访问表及队列。

关键点总结

[!green]

  • 合法不等于可达：只有通过已可达邻居进入的格子才加入搜索。
  • 入队即标记：避免不同方向在同一格出队前反复发现它。
  • 数位条件不能代替路径条件：数位和不随坐标单调变化，允许进入的格子也可能被隔离。
  • 先边界后访问数组：合法性检查顺序保证不会读取越界下标。

易错点总结

[!yellow]

  • 只统计所有数位合法的坐标，会把不连通位置也算进去。
  • 通过越界或非法格子继续扩展，会穿过本来不可走的区域。
  • 同一位置多次入队并重复计数，会高估答案。

相似题目

题目 难度 关联与区别
695. 岛屿的最大面积 中等 同样统计从某个起点可达的网格分量，本题合法格由坐标数位和动态判定，而非输入矩阵给定。
200. 岛屿数量 中等 同样必须避免重复访问，本题只统计原点可达部分，不是统计整个网格所有连通块。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/41608047
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！