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

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
地上有一个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：

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

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

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

思路

我第一次想到这个题首先想到的是暴力破解，它不是让寻找次数吗，这样我用暴力破解不是效率最快的吗？

两个for循环遍历，然后在一个if判断，这样不是直接就能找到了。

结果发现，我少了一个重要的条件，就是可达性。机器人是一个坐标一个坐标移动的，如果中间有的坐标到不了，那么后面的一部分坐标也都到达不了。

img

例如：这张图片里面，黄色的位置都是理论上可以到达，但是实际上到达不了的。

如果是用的for循环，肯定会计算错误而且浪费性能。

因为只需要判断这一个点是否满足，所以不需要回溯。

实现

DFS

DFS 是朝一个方向走到底，再回退，

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
private static class Solution {

    public int movingCount(int m, int n, int k) {
        boolean[][] vis = new boolean[m][n];
        return solve(0, 0, m, n, vis, k);
    }

    private int solve(int x, int y, int m, int n, boolean[][] vis, int k) {
        if (x >= m || y >= n || vis[x][y] || (getPlaces(x) + getPlaces(y)) > k) {
            return 0;
        }
        vis[x][y] = true;
        // 先在横向上一直深度遍历
        return 1 + solve(x + 1, y, m, n, vis, k) + solve(x, y + 1, m, n, vis, k);

    }
}
public static int getPlaces(int num) {
    int s = 0;
    while (num != 0) {
        s += num % 10;
        num = num / 10;
    }
    return s;
}

时间复杂度：O(MN)

空间复杂度：O(MN)

BFS

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

public static int getPlaces(int num) {
    int s = 0;
    while (num != 0) {
        s += num % 10;
        num = num / 10;
    }
    return s;
}

private static class Solution2 {
    public int movingCount(int m, int n, int k) {
        int res = 0;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            assert poll != null;
            int x = poll[0];
            int y = poll[1];
            if (x >= m || y >= n || vis[x][y] || (getPlaces(poll[0]) + getPlaces(poll[1])) > k) {
                continue;
            }
            res++;
            vis[x][y] = true;
            queue.add(new int[]{x + 1, y});
            queue.add(new int[]{x, y + 1});

        }
        return res;
    }
}

这个就是普通的DFS遍历

博客首先发布于：

https://lvxiaoyi.top/