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
| var directs = [4][2]int{{-1,0},{0,-1},{1,0},{0,1}}
var ans int
func movingCount(m int, n int, k int) int {
var visited = make([][]bool,m)
for i:=0 ; i<m;i++{
visited[i] = make([]bool,n)
}
ans = 0
backtrack(visited,m,n,0,0,k)
return ans
}
func backtrack(visited [][]bool,m,n,i,j,k int){
if i<0 || i>=m || j<0 || j>=n || visited[i][j] || add(i,j) > k {return}
visited[i][j]=true
ans++
for _,v := range directs{
backtrack(visited,m,n,i+v[0],j+v[1],k)
}
}
func add(m,n int) int{
sum := 0
for m!=0 || n != 0{
sum += m%10 + n%10
m = m/10
n = n/10
}
return sum
}
|
