엔지니어 게시판
LeetCode 솔루션 분류

[7/16] 576. Out of Boundary Paths

컨텐츠 정보

본문

Medium
1591185Add to ListShare

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 mnmaxMovestartRowstartColumn, 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 <= 50
  • 0 <= maxMove <= 50
  • 0 <= startRow < m
  • 0 <= 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.
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)
전체 404 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 763 명
  • 오늘 방문자 6,112 명
  • 어제 방문자 6,975 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,537 명
알림 0