# 题目链接
# 题目描述
地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,每一次只能向左右上下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
例如,当 k 为 18 时,机器人能够进入方格 (35,37),因为 3+5+3+7=18。但是,它不能进入方格 (35,38),因为 3+5+3+8=19。请问该机器人能够达到多少个格子?
# 解题思路
func movingCount(m int, n int, k int) int {
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
return dfs(m, n, 0, 0, k, dp)
}
func dfs(m, n, i, j, k int, dp [][]int) int {
if i < 0 || j < 0 || i >= m || j >= n || dp[i][j] == 1 || (sumPos(i)+sumPos(j)) > k {
return 0
}
dp[i][j] = 1
sum := 1
sum += dfs(m, n, i, j+1, k, dp)
sum += dfs(m, n, i, j-1, k, dp)
sum += dfs(m, n, i+1, j, k, dp)
sum += dfs(m, n, i-1, j, k, dp)
return sum
}
// 求所有位之和
func sumPos(n int) int {
var sum int
for n > 0 {
sum += n % 10
n = n / 10
}
return sum
}
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
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