题目
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路
本题仍然使用回溯法，这题比《剑指offer——65 矩阵中的路径》简单，直接上代码
存在几个问题：
- 需要判断机器人是否可以访问到该点
- 需要计算各位和
注意：本题需要注意的是，因为机器人是从（0，0）出发，所以其实并不用遍历四向，遍历两个方向即可
代码
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
| function movingCount (threshold, rows, cols) {
if (threshold === 0) return 0
let visited = new Array(rows * cols).fill(false)
return moving(threshold, rows, cols, 0, 0, visited)
}
function moving (threshold, rows, cols, i, j, visited) {
let count = 0
if (callArrive(threshold, rows, cols, i, j, visited)) {
count = 1
visited[i * cols + j] = true
count += moving(threshold, rows, cols, i, j + 1, visited)
count += moving(threshold, rows, cols, i + 1, j, visited)
}
return count
}
function callArrive (threshold, rows, cols, i, j, visited) {
if (i >= rows || j >= cols || visited[i * cols + j]) return false
return bitSum(i) + bitSum(j) <= threshold
}
function bitSum (n) {
let sum = 0
while (n) {
sum += n % 10
n = Math.floor(n / 10)
}
return sum
}
|
