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
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 = [ * C for _ in xrange(R)] nxt[sr][sc] = 1 ans = 0 for time in xrange(N): cur = nxt nxt = [ * 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
@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
@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.