Python, Straightforward with Explanation


  • 4

    At time t, let's maintain cur[r][c] = the number of paths to (r, c) with t moves, and nxt[r][c] = the number of paths to (r, c) with t+1 moves.

    A ball at (r, c) at time t, can move in one of four directions. If it stays on the board, then it contributes to a path that takes t+1 moves. If it falls off the board, then it contributes to the final answer.

    def findPaths(self, R, C, N, sr, sc):
        MOD = 10**9 + 7
        nxt = [[0] * C for _ in xrange(R)]
        nxt[sr][sc] = 1
        
        ans = 0
        for time in xrange(N):
            cur = nxt
            nxt = [[0] * C for _ in xrange(R)]
            for r, row in enumerate(cur):
                for c, val in enumerate(row):
                    for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                        if 0 <= nr < R and 0 <= nc < C:
                            nxt[nr][nc] += val
                            nxt[nr][nc] %= MOD
                        else:
                            ans += val
                            ans %= MOD
            
        return ans
    

  • 0
    L

    @awice Do you got any tips on coming up with the DP solution? I have the same DFS code you do and got Time exceeded, but couldn't figure out how to apply the DP. I posted mine here https://discuss.leetcode.com/topic/88888/how-to-turn-this-solution-into-a-dp-solution-tle


  • 1

    @livelearn Make sure you are not visiting the same nodes/state multiple times. You can use a visitor pattern: add the node to a set whenever you add it to q. You can check to only add nodes to q that are not in your set.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.