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


  • 0
    A

    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;
        }
    };
    

Log in to reply
 

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