# 576. Out of Boundary Paths 出界的路径数

@TOC

## # 题目描述

There is an `m` by `n` grid with a ball. Given the start coordinate `(i,j)` of the ball, you can move the ball to `adjacent` cell or cross the grid boundary in four directions (up, down, left, right). However, you can `at most` move `N` times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod `10^9 + 7`.

Example 1:

``````Input: m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:
``````

Example 2:

``````Input: m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:
``````

Note:

1. Once you move the ball out of boundary, you cannot move it back.
2. The length and height of the grid is in range [1,50].
3. N is in range [0,50].

## # 解题方法

### # 动态规划

``````class Solution(object):
def findPaths(self, m, n, N, i, j):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
dp = [[[0] * n for _ in range(m)] for _ in range(N + 1)]
for s in range(1, N + 1):
for x in range(m):
for y in range(n):
v1 = 1 if x == 0 else dp[s - 1][x - 1][y]
v2 = 1 if x == m - 1 else dp[s - 1][x + 1][y]
v3 = 1 if y == 0 else dp[s - 1][x][y - 1]
v4 = 1 if y == n - 1 else dp[s - 1][x][y + 1]
dp[s][x][y] = (v1 + v2 + v3 + v4) % (10**9 + 7)
return dp[N][i][j]
``````

``````class Solution(object):
def findPaths(self, m, n, N, i, j):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
dp = [[0] * n for _ in range(m)]
for s in range(1, N + 1):
curStatus = [[0] * n for _ in range(m)]
for x in range(m):
for y in range(n):
v1 = 1 if x == 0 else dp[x - 1][y]
v2 = 1 if x == m - 1 else dp[x + 1][y]
v3 = 1 if y == 0 else dp[x][y - 1]
v4 = 1 if y == n - 1 else dp[x][y + 1]
curStatus[x][y] = (v1 + v2 + v3 + v4) % (10**9 + 7)
dp = curStatus
return dp[i][j]
``````

### # 状态搜索

``````class Solution(object):
def findPaths(self, m, n, N, i, j):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
dp = [[[0] * n for _ in range(m)] for _ in range(N + 1)]
ds = [(0, 1), (0, -1), (-1, 0), (1, 0)]
for s in range(1, N + 1):
for x in range(m):
for y in range(n):
for d in ds:
nx, ny = x + d[0], y + d[1]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
dp[s][x][y] += 1
else:
dp[s][x][y] = (dp[s][x][y] + dp[s - 1][nx][ny]) % (10**9 + 7)
return dp[N][i][j]
``````

``````class Solution(object):
def findPaths(self, m, n, N, i, j):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
dp = [[0] * n for _ in range(m)]
ds = [(0, 1), (0, -1), (-1, 0), (1, 0)]
for s in range(1, N + 1):
curStatus = [[0] * n for _ in range(m)]
for x in range(m):
for y in range(n):
for d in ds:
nx, ny = x + d[0], y + d[1]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
curStatus[x][y] += 1
else:
curStatus[x][y] = (curStatus[x][y] + dp[nx][ny]) % (10**9 + 7)
dp = curStatus
return dp[i][j]
``````

### # 记忆化搜索

``````class Solution(object):
def findPaths(self, m, n, N, i, j):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
dp = [[[0] * n for _ in range(m)] for _ in range(N + 1)]
return self.dfs(m, n, N, i, j, dp)

def dfs(self, m, n, N, x, y, dp):
if N == 0:
return 0
if x < 0 or x >= m or y < 0 or y >= n:
return 1
if dp[N][x][y]:
return dp[N][x][y]
ds = [(0, 1), (0, -1), (-1, 0), (1, 0)]
for d in ds:
nx, ny = x + d[0], y + d[1]
dp[N][x][y] = (dp[N][x][y] + self.dfs(m, n, N - 1, nx, ny, dp)) % (10**9 + 7)
return dp[N][x][y]
``````