【算法】机器人运动范围

发表于 阅读次数：

剑指 Offer 第 13 题-机器人运动范围

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

错误案例

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
public class Jz13_1_wrong {
    public static void main(String[] args) {
        System.out.println(movingCount(1, 2, 3));
        System.out.println(movingCount(0, 1, 3));
        System.out.println(movingCount(10, 1, 100));
        System.out.println(movingCount(5, 10, 10));
        System.out.println(movingCount(15, 100, 100));
        System.out.println(movingCount(18, 36, 38));
    }


    /**
     * 错误的解法：题目要求，每次只能向左、右、上、下移动。下面的代码没考虑这个，导致跨越的格也存在，会多算
     */
    private static int movingCount(int threshold, int rows, int cols) {
        if (rows == 0 || cols == 0) {
            return 0;
        }

        int count = 0;
        for (int i = 0; i < rows; i++) {

            // 如果i本身就不满足，就不用向后走了
            if (!reachable(i, 0, threshold)) {
                break;
            }

            for (int j = 0; j < cols; j++) {

                // 如易j本身就不满足，就不用向后走了
                if (!reachable(0, j, threshold)) {
                    break;
                }

                // 根据 threshold，判断 (i,j) 是否可达
                if (reachable(i, j, threshold)) {
                    count++;
                    System.out.printf("(%d,%d)%n", i, j);
                }
            }
        }
        return count;
    }

    private static boolean reachable(int i, int j, int threshold) {
        final int sum = getSum(i) + getSum(j);
        return sum <= threshold;
    }

    private static int getSum(int a) {
        int sum = 0;
        while (a > 0) {
            sum += a % 10;
            a = a / 10;
        }
        return sum;
    }
}

正确的 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class Jz13_2 {

    public static void main(String[] args) {
        System.out.println(new Jz13_2().movingCount(1, 2, 3));
        System.out.println(new Jz13_2().movingCount(0, 1, 3));
        System.out.println(new Jz13_2().movingCount(10, 1, 100));
        System.out.println(new Jz13_2().movingCount(5, 10, 10));
        System.out.println(new Jz13_2().movingCount(18, 36, 38));
        System.out.println(new Jz13_2().movingCount(15, 100, 100));
    }


    int movingCount = 0;

    /**
     * DFS 遍历
     */
    public int movingCount(int threshold, int rows, int cols) {
        if (rows == 0 || cols == 0) {
            return 0;
        }

        movingCount = 0;
        boolean[][] arr = new boolean[rows][cols];
        dfs(arr, rows, cols, 0, 0, threshold);
        return movingCount;
    }

    /**
     * 模板：
     * <p>
     * 检查下标
     * 检查是否被访问过，或者是否满足当前匹配条件
     * 检查是否满足返回结果条件
     * 标记
     * 进入下下一步递归
     * 回溯
     */

    private void dfs(boolean[][] arr, int rows, int cols, int i, int j, int threshold) {
        // 检查下标
        if (i < 0 || j < 0 || i >= rows || j >= cols) {
            return;
        }

        // 检查是否被访问过
        if (arr[i][j]) {
            return;
        }

        // 检查是否满足条件
        if (!reachable(i, j, threshold)) {
            return;
        }

        arr[i][j] = true;
        movingCount++;

        // 下一个
        dfs(arr, rows, cols, i + 1, j, threshold); // 右
        dfs(arr, rows, cols, i, j + 1, threshold); // 下
        dfs(arr, rows, cols, i - 1, j, threshold); // 左
        dfs(arr, rows, cols, i, j - 1, threshold); // 上
    }

    private boolean reachable(int i, int j, int threshold) {
        final int sum = getSum(i) + getSum(j);
        return sum <= threshold;
    }

    private int getSum(int a) {
        int sum = 0;
        while (a > 0) {
            sum += a % 10;
            a = a / 10;
        }
        return sum;
    }
}

正确的 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class Jz13_3 {

    public static void main(String[] args) {
        System.out.println(new Jz13_3().movingCount(1, 2, 3));
        System.out.println(new Jz13_3().movingCount(0, 1, 3));
        System.out.println(new Jz13_3().movingCount(10, 1, 100));
        System.out.println(new Jz13_3().movingCount(5, 10, 10));
        System.out.println(new Jz13_3().movingCount(18, 36, 38));
        System.out.println(new Jz13_3().movingCount(15, 100, 100));
    }


    // 用栈来实现
    public int movingCount(int threshold, int rows, int cols) {
        if (rows == 0 || cols == 0) {
            return 0;
        }

        int movingCount = 0;
        boolean[][] arr = new boolean[rows][cols];

        Stack<Pair<Integer, Integer>> stack = new Stack<>();
        // 第一个入栈
        stack.push(new Pair<>(0, 0));

        while (!stack.isEmpty()) {
            // 出栈，标记
            final Pair<Integer, Integer> pop = stack.pop();
            final Integer x = pop.getKey();
            final Integer y = pop.getValue();
            arr[x][y] = true;
            movingCount++;

            // 并将周围入栈（检测边界和条件）

            // 右
            if (border(x + 1, y, rows, cols) && reachable(x + 1, y, threshold) && !arr[x + 1][y]) {
                stack.push(new Pair<>(x + 1, y));
                arr[x + 1][y] = true;
            }

            // 下
            if (border(x, y + 1, rows, cols) && reachable(x, y + 1, threshold) && !arr[x][y + 1]) {
                stack.push(new Pair<>(x, y + 1));
                arr[x][y + 1] = true;
            }

            // 左
            if (border(x - 1, y, rows, cols) && reachable(x - 1, y, threshold) && !arr[x - 1][y]) {
                stack.push(new Pair<>(x - 1, y));
                arr[x - 1][y] = true;
            }

            // 上
            if (border(x, y - 1, rows, cols) && reachable(x, y - 1, threshold) && !arr[x][y - 1]) {
                stack.push(new Pair<>(x, y - 1));
                arr[x][y - 1] = true;
            }

        }


        return movingCount;
    }

     // 检查边界
    private boolean border(int i, int j, int rows, int cols) {
        return i >= 0 && i < rows && j >= 0 && j < cols;
    }

    // 检查是否可达
    private boolean reachable(int i, int j, int threshold) {
        final int sum = getSum(i) + getSum(j);
        return sum <= threshold;
    }

    // 获取数字自身之和
    private int getSum(int a) {
        int sum = 0;
        while (a > 0) {
            sum += a % 10;
            a = a / 10;
        }
        return sum;
    }

    public static class Pair<K, V> {

        private final K key;
        private final V value;

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

正确的 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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class Jz13_4 {

    public static void main(String[] args) {
        System.out.println(new Jz13_4().movingCount(1, 2, 3));
        System.out.println(new Jz13_4().movingCount(0, 1, 3));
        System.out.println(new Jz13_4().movingCount(10, 1, 100));
        System.out.println(new Jz13_4().movingCount(5, 10, 10));
        System.out.println(new Jz13_4().movingCount(18, 36, 38));
        System.out.println(new Jz13_4().movingCount(15, 100, 100));
    }


    // BFS遍历：用栈来实现
    public int movingCount(int threshold, int rows, int cols) {
        if (rows == 0 || cols == 0) {
            return 0;
        }

        int movingCount = 0;
        boolean[][] arr = new boolean[rows][cols];

        Stack<Pair<Integer, Integer>> stack = new Stack<>();
        // 将第一个入栈
        stack.push(new Pair<>(0, 0));

        // 方向组合，newX=dirs[i], newY=dirs[i+1]，分别对应【左（-1，0）、下（0，1）、右（1，0）、上（0，-1）】
        int[] dirs = new int[]{-1, 0, 1, 0, -1};

        while (!stack.isEmpty()) {
            // 出栈，标记
            final Pair<Integer, Integer> pop = stack.pop();
            final Integer x = pop.getKey();
            final Integer y = pop.getValue();

            // 设置为true，表示访问过了，不可重复访问
            arr[x][y] = true;
            movingCount++;

            // 并将周围入栈（检测边界和条件）
            for (int i = 0; i < dirs.length; i++) {
                int newX = dirs[i];
                int newY = dirs[i + 1];
                if (border(newX, newY, rows, cols) && reachable(newX, newY, threshold) && !arr[newX][newY]) {
                    stack.push(new Pair<>(newX, newY));
                    arr[newX][newY] = true;
                }
            }
        }


        return movingCount;
    }

    // 检查边界
    private boolean border(int i, int j, int rows, int cols) {
        return i >= 0 && i < rows && j >= 0 && j < cols;
    }

    // 检查是否可达
    private boolean reachable(int i, int j, int threshold) {
        final int sum = getSum(i) + getSum(j);
        return sum <= threshold;
    }

    // 获取数字自身之和
    private int getSum(int a) {
        int sum = 0;
        while (a > 0) {
            sum += a % 10;
            a = a / 10;
        }
        return sum;
    }

    public static class Pair<K, V> {

        private final K key;
        private final V value;

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}