aboutsummaryrefslogtreecommitdiff
path: root/oob_path.py
blob: 63a9641ce71be86a255f34d4b294331269e111b8 (plain)
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 576. Out of Boundary Paths

"""
there is an 'm  n' grid with a ball. the ball is initially at the position
'[start_row, start_column]'. you are allowed to move the ball to one of the
four adjacent cells in the grid (possible out of the grid crossing the grid
boundary). you can apply at most 'max_move' moves to the ball. given the give
integers, 'm', 'n', 'max_move', 'start_row', 'and start_column', 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
"""


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
        """
        dp = [[[-1] * (maxMove + 1) for _ in range(n + 1)] for _ in range(m + 1)]

        def solve(i, j, maxMove):
            if maxMove < 0:
                return 0
            if i < 0 or i >= m or j < 0 or j >= n:
                return 1
            if dp[i][j][maxMove] != -1:
                return dp[i][j][maxMove]
            a = solve(i - 1, j, maxMove - 1)
            b = solve(i + 1, j, maxMove - 1)
            c = solve(i, j - 1, maxMove - 1)
            d = solve(i, j + 1, maxMove - 1)
            dp[i][j][maxMove] = a + b + c + d
            return dp[i][j][maxMove]

        return solve(startRow, startColumn, maxMove) % 1000000007


if __name__ == "__main__":
    obj = Solution()
    print(obj.findPaths(m=2, n=2, maxMove=2, startRow=0, startColumn=0))  # expect: 6
    print(obj.findPaths(m=1, n=3, maxMove=3, startRow=0, startColumn=1))  # expect: 12