鏈接：https://leetcode-cn.com/problems/out-of-boundary-paths
package leetcode
func FindPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
mod := 1000000007
flag := make([][][]int, m, m)
for i := 0; i < m; i++ {
flag[i] = make([][]int, n, n)
for j := 0; j < n; j++ {
flag[i][j] = make([]int, maxMove+1, maxMove+1)
for t := 1; t <= maxMove; t++ {
flag[i][j][t] = -1
}
}
}
var deep func(move, x, y int) int
deep = func(move, x, y int) int {
count := flag[x][y][move]
if count != -1 {
return count
}
count = 0
if move == 1 {
if x-1 < 0 {
count++
}
if x+1 >= m {
count++
}
if y-1 < 0 {
count++
}
if y+1 >= n {
count++
}
flag[x][y][move] = count % mod //存儲(chǔ)
return count
}
if x-1 >= 0 {
count += deep(move-1, x-1, y)
}
if x+1 < m {
count += deep(move-1, x+1, y)
}
if y-1 >= 0 {
count += deep(move-1, x, y-1)
}
if y+1 < n {
count += deep(move-1, x, y+1)
}
flag[x][y][move] = count % mod //存儲(chǔ)
return count % mod
}
var sum int
for i := 1; i <= maxMove; i++ {
sum += deep(i, startRow, startColumn)
}
return sum % mod
}
