leetcode-go/leetcode/medium/576.out-of-boundary-paths.go

const MOD int = 1000000007

var dy = []int{0, 1, 0, -1}
var dx = []int{1, 0, -1, 0}

func findPaths(m int, n int, N int, i int, j int) int {
	var dp [50][50]int
	for k := 0; k < N; k++ {
		var nxt [50][50]int
		for y := 0; y < m; y++ {
			for x := 0; x < n; x++ {
				for d := 0; d < 4; d++ {
					ny, nx := y+dy[d], x+dx[d]
					if ny == -1 || ny == m || nx == -1 || nx == n {
						nxt[y][x]++
					} else {
						nxt[y][x] = (nxt[y][x] + dp[ny][nx]) % MOD
					}
				}
			}
		}
		dp = nxt
	}
	return dp[i][j]
}