aboutsummaryrefslogtreecommitdiff
path: root/oob_path.py
diff options
context:
space:
mode:
Diffstat (limited to 'oob_path.py')
-rw-r--r--oob_path.py46
1 files changed, 46 insertions, 0 deletions
diff --git a/oob_path.py b/oob_path.py
new file mode 100644
index 0000000..63a9641
--- /dev/null
+++ b/oob_path.py
@@ -0,0 +1,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