剑指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. 机器人的运动范围__牛客网