###### tags: `Leetcode` `medium` `dynamic programming` `python`

# 576. Out of Boundary Paths

## [題目連結:] https://leetcode.com/problems/out-of-boundary-paths/

## 題目:
There is an ```m x n``` grid with a ball. The ball is initially at the position ```[startRow, startColumn]```. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply **at most** ```maxMove``` moves to the ball.

Given the five integers ```m, n, maxMove, startRow, startColumn```, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it **modulo** ```10^9 + 7```.


#### [圖片來源] https://leetcode.com/problems/out-of-boundary-paths/

## 解題想法:
* 題目給一個二維數組，在某個位置放置足球，每次可以上下左右方向移動移步，要求走最多maxMove步後，可以出界，求總共移動方法數。
* 結果會太大，要求modulo 10**9+7
* **dp[k][i][j]:總共走k步，從(i,j)位置走出界的總方法數**
* 相當於周圍四個位置走k-1步出界的總路徑和
* 當(i,j)處於邊界時，只要走移1步即可移動到界外
* dp[k][i][j]=top+bottom+left+right
* **top**= 1 if i==0 else dp[k-1][i-1][j]
* **bottom**=1 if i==m-1 else dp[k-1][i+1][j]
* **left**=1 if j==0 else dp[k-1][i][j-1]
* **right**=1 if j==n-1 else dp[k-1][i][j+1]

## Python:

class Solution(object):
    def findPaths(self, m, n, maxMove, startRow, startColumn):
        """
        :type m: int
        :type n: int
        :type maxMove: int
        :type startRow: int
        :type startColumn: int
        :rtype: int
        """
        #init
        dp=[ [ [0 for _ in range(n)] for _ in range(m)] for _ in range(maxMove+1)]
        #dp從1步開始
        for k in range(1,maxMove+1):
            for i in range(m):
                for j in range(n):
                    top=1 if i==0 else dp[k-1][i-1][j]
                    bottom=1 if i==m-1 else dp[k-1][i+1][j]
                    left=1 if j==0 else dp[k-1][i][j-1]
                    right=1 if j==n-1 else dp[k-1][i][j+1]
                    dp[k][i][j]=(top+bottom+left+right)%(10**9+7)
        return dp[maxMove][startRow][startColumn]

if __name__ == '__main__':
    result=Solution()
    ans=result.findPaths(m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1)
    print(ans)