# Python, O(N*(N+R+C)) reduction to 1D [Very Fast]

• Following @StefanPochmann 's excellent suggestion, let `inside(t)` be the number of paths that remain inside the board after `t` moves. Then the number of paths that exit the boundary on the `t+1`'th move is `4*inside(t) - inside(t+1)`.

Suppose we are to make `t` moves. We'll make `k` horizontal moves and `t-k` vertical moves. We can shuffle the order of these moves in `binom(t, k)` ways (the binomial coefficient.) So in total:
`inside(t) = sum_{k=0..t} (number of ways to stay on the board in k moves horizontally) * (number of ways to stay on the board in t-k moves vertically) * binom(t, k)`.

We can find in advance our answers to the 1D problem by a simple dp. There probably exists an even faster approach for this, but I can't think of one right now.

``````def findPaths(self, R, C, N, sr, sc):
MOD = 10**9 + 7

def binom_all(n):
ans = [1]
r = 1
for i in xrange(1, n+1):
r *= n - i + 1
r /= i
ans.append(r)
return ans

def solve_1D(A):
ans = [1]
for time in xrange(N+1):
Anew = [0] * len(A)
inside = 0
for i, u in enumerate(A):
if i >= 1:
Anew[i-1] += u
inside += u
if i < len(A) - 1:
Anew[i+1] += u
inside += u
A = Anew
ans.append(inside)
return ans
dprow = solve_1D([+(r == sr) for r in xrange(R)])
dpcol = solve_1D([+(c == sc) for c in xrange(C)])
binoms = [binom_all(n) for n in xrange(N+1)]

def inside(t):
ans = 0
for k in xrange(t+1):
ans += dprow[k] * dpcol[t-k] * binoms[t][k]
return ans % MOD

S = sum(inside(t) for t in xrange(N))
return (3*S - inside(N) + inside(0))%MOD
``````

• Excellent. That was a neat trick of using 4*inside(t) - inside(t+1).

I used slightly different technique but the essence is the same. I instead also calculated number of ways to reach the boundary in a 1D array and used that to calculate the number of ways to exit the boundary.
I like your trick better though. :)

``````class Solution {
public:
using LL = long long;
int findPaths(int m, int n, int N, int i, int j) {
if (n==0 || m==0) return 0;

int mod = 1000000007;

// using dynamic programming to calculate combinations.
LL C[52][52];
C[0][0] = C[0][1] = 1;
for (int a=1; a<=N; a++) {
C[a][0] = C[a][a] = 1;
for (int b=1; b<a; b++)
C[a][b] = (C[a-1][b] + C[a-1][b-1]) % mod;
}

vector<LL> H(N+2,0), V(N+2, 0);  // H = Horizontal, V = Vertical
vector<LL> HB(N+2,0), VB(N+2, 0);  // HB = Horizontal Boundary, VB = Vertical Boundary
LL dp[2][52];
int t = 0;

// using dynamic programming to calculate number of ways you can move in straight line (vertically or horizontally)
// in s steps and still be inside the island boundaries.
memset(dp,0,sizeof dp);
dp[t][i+1] = 1;
V[0] = 1; VB[0] = (i+1==1) + (i+1==m);
for (int s=1; s<=N; s++) {
t = !t;
for (int a=1; a<=m; a++)
V[s] += dp[t][a] = (dp[!t][a-1] + dp[!t][a+1]) % mod;
VB[s] = (dp[t][1] + dp[t][m]) % mod;
V[s] %= mod;
}
memset(dp,0,sizeof dp);
dp[t][j+1] = 1;
H[0] = 1; HB[0] = (j+1==1) + (j+1==n);
for (int s=1; s<=N; s++) {
t = !t;
for (int b=1; b<=n; b++)
H[s] += dp[t][b] = (dp[!t][b-1] + dp[!t][b+1]) % mod;
HB[s] += (dp[t][1] + dp[t][n]) % mod;
H[s] %= mod;
}

// To calculate number of ways you will be at any boundary in s steps
// let dx be horizontal movement in s steps. we can do that in C[s][dx] ways.
// H[dx] * VB[s-dx] = number of ways you are inside the island moving horizontally dx times and at the vertical boundary in s-dx vertical movements.
LL count = 0;
for(int s=0; s<N; s++) {
for(int dx=0; dx<=s; dx++) {
LL t = ((H[dx] * VB[s-dx]) % mod + (HB[dx] * V[s-dx]) % mod) % mod;
count = (count + (C[s][dx] * t) % mod) % mod;
}
}

// Total complexity O(N^2 + N*(m+n))
return count;
}
};
``````

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