咸鱼回响

望之天回,即之云昏

0%

【剑指 offer】13. 机器人的运动范围

发表于 更新于

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

题目描述

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

1
2
输入：m = 2, n = 3, k = 1
输出：3

示例 2：

1
2
输入：m = 3, n = 1, k = 0
输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

我的解题

思路

题目中给了一个限定条件不能进入行坐标和列坐标的数位之和大于k的格子，即从点（0，0）出发的机器人在这个条件内能都达到的所有方块数量，同时要注意，所有能够到达的方块都是和点（0，0）连续的，例如当k=2时候，点（100，100），光看k的值是满足的但是机器人无法到达这个点。

这种涉及到连续路径查询，且只需要查询个数不需要查询具体某条路线的问题可以用广度优先搜索来完成。

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public int movingCount(int m, int n, int k) {
        //广度优先搜索
        Queue<int[]> queue = new LinkedList<>();
        Set<String> used = new HashSet<>();
        used.add("0,0");
        queue.add(new int[] {0, 0});
        int[][] foots = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
        };
        int count = 0;

        while (!queue.isEmpty()) {
            int[] num = queue.poll();
            int mK = getK(num[0], num[1]);
            if (mK > k) {
                continue;
            }

            for (int[] foot : foots) {
                int x = foot[0] + num[0];
                int y = foot[1] + num[1];
                if (x < 0 || y < 0 || x >= m || y >= n) {
                    continue;
                }
                String key = x + "," + y;
                if (used.contains(key)) {
                    continue;
                }
                used.add(key);

                if (getK(x, y) > k) {
                    continue;
                }
                queue.add(new int[] {x, y});
            }

            count++;
        }
        return count;
    }

    private int getK(int i, int j) {
        int sum = 0;
        while (i > 0) {
            int n = i % 10;
            sum += n;
            i /= 10;
        }
        while (j > 0) {
            int n = j % 10;
            sum += n;
            j /= 10;
        }
        return sum;
    }

}

最优解

思路

思路一：广度优先搜索

不过在

1
2
3
4
5
6
int[][] foots = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}
};

这一步可以用

1
2
3
4
int[][] foots = {
    {1, 0},
    {0, 1}
};

来替代，用于减少循环次数，因为机器人只会往右或下行走。

思路二：递推

考虑到方法一提到搜索的方向只需要朝下或朝右，我们可以得出一种递推的求解方法。
定义 vis[i][j] 为 (i, j) 坐标是否可达，如果可达返回 1，否则返回 0。
首先 (i, j) 本身需要可以进入，因此需要先判断 i 和 j 的数位之和是否大于 k ，如果大于的话直接设置 vis[i][j] 为不可达即可。
否则，前面提到搜索方向只需朝下或朝右，因此 (i, j) 的格子只会从 (i - 1, j) 或者 (i, j - 1) 两个格子走过来（不考虑边界条件），那么 vis[i][j] 是否可达的状态则可由如下公式计算得到：

vis[i][j]=vis[i−1][j] or vis[i][j−1]

即只要有一个格子可达，那么 (i, j) 这个格子就是可达的，因此我们只要遍历所有格子，递推计算出它们是否可达然后用变量 ans 记录可达的格子数量即可。
初始条件 vis[i][j] = 1 ，递推计算的过程中注意边界的处理。

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k) {
                    continue;
                }
                // 边界判断
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}