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

发表于 更新于 分类于 阅读次数：

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

解答1[Java]：递归算法

核心思想

回溯的思想。

使用一个布尔类型的数组标记所有格子是都已经被访问过了。

代码

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
public class Solution {
    public int movingCount(int threshold, int rows, int columns) {
        if (threshold < 0 || rows <= 0 || columns <= 0) {
            return 0;
        }

        boolean[] visited = new boolean[rows * columns];
        int count = 0;

        count = movingCountCore(threshold, rows, columns, 0, 0, visited);

        return count;
    }

    private int movingCountCore(int threshold, int rows, int columns, int row, int column, boolean[] visited) {
        int count = 0;
        if (check(threshold, rows, columns, row, column, visited)) {
            visited[row * columns + column] = true;

            count = 1 + movingCountCore(threshold, rows, columns, row - 1, column, visited)
                    + movingCountCore(threshold, rows, columns, row + 1, column, visited)
                    + movingCountCore(threshold, rows, columns, row, column - 1, visited)
                    + movingCountCore(threshold, rows, columns, row, column + 1, visited);
        }

        return count;
    }

    private boolean check(int threshold, int rows, int columns, int row, int column, boolean[] visited) {
        return row >= 0 && row < rows && column >= 0 && column < columns
                && getDigitSum(row) + getDigitSum(column) <= threshold
                && !visited[row * columns + column];
    }

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

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

        return sum;
    }
}

解答2[Java]：非递归算法

核心思想

代码

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
import java.util.Stack;

public class Solution {
    public int movingCount(int threshold, int rows, int cols) {
        if (rows <= 0 || cols <= 0 || threshold < 0) {
            return 0;
        }
        Stack<Integer> s = new Stack<>();
        boolean[] visited = new boolean[rows * cols];
        int[][] xoy = {{0, 1, 0, -1}, {1, 0, -1, 0}};
        int count = 0;
        s.add(0);
        visited[0] = true;
        while (!s.empty()) {
            int cur = s.pop();
            count++;
            // 一个格子的坐标可以根据线性顺序和列数算出
            for (int i = 0; i < 4; i++) {
                int x = cur % cols + xoy[0][i];
                int y = cur / cols + xoy[1][i];
                int sum = getDigitSum(x) + getDigitSum(y);
                if (x >= 0 && x < cols && y >= 0 && y < rows
                        && sum <= threshold && !visited[x + y * cols]) {
                    s.add(x + y * cols);
                    visited[x + y * cols] = true;
                }
            }
        }
        return count;
    }

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

参考资料

  1. 机器人的运动范围__牛客网