LeetCode 솔루션 분류
[7/16] 576. Out of Boundary Paths
본문
Medium
1591185Add to ListShareThere 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 109 + 7.
Example 1:
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 Output: 6
Example 2:
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1 Output: 12
Constraints:
1 <= m, n <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n
Accepted
66,826
Submissions
165,241
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 160 ms, faster than 72.89% of Python3 online submissions for Out of Boundary Paths.
Memory Usage: 19.2 MB, less than 40.66% of Python3 online submissions for Out of Boundary Paths.
Memory Usage: 19.2 MB, less than 40.66% of Python3 online submissions for Out of Boundary Paths.
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
memo = {}
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(move, r, c):
if move < 0: return 0
if not (0<=r<m and 0<=c<n): return 1
if (move,r,c) not in memo:
res = 0
for r_dir, c_dir in directions:
new_r, new_c = r+r_dir, c+c_dir
res += dfs(move-1, new_r, new_c)
memo[(move,r,c)] = res%(10**9+7)
return memo[(move,r,c)]
return dfs(maxMove, startRow, startColumn)
