使用dfs来做
func movingCount(k int, m int, n int) int {
// 定义位置 不能被重复使用
pos := make([][]int, m)
for i, _ := range pos {
pos[i] = make([]int, n)
}
// 使用dfs来遍历每一个格子
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
return dfs(m, n, i, j, k, pos)
}
}
return 0
}
func dfs(m, n, i, j, k int, pos [][]int) int {
if i < 0 || j <0 || i == m || j == n || pos[i][j] == 1 || compute(i, j) > k {
return 0
}
// 当前格子的值小于等于k 将当前格子置为1 不再遍历
pos[i][j] = 1
sum := 1
sum += dfs(m, n, i+1, j, k, pos)
sum += dfs(m, n, i-1, j, k, pos)
sum += dfs(m, n, i, j+1, k, pos)
sum += dfs(m, n, i, j-1, k, pos)
return sum
}
func compute(i, j int) int {
return i % 10 + i / 10 + j % 10 + j / 10
}