# O(N*N + (m+n)*N) The fastest solution.

• Involves a bit of math.

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