# Python, Straightforward with Explanation

• 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
``````

• @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.

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