Java clear solution, iteration


  • 0
    Q
    public class Solution {
        public int findPaths(int m, int n, int N, int i, int j) {
            if(N<=0) return 0;
            //get level 1.
            int[][] matrix = new int[m][n];
            for(int a=0;a<m;a++){
                for(int b=0;b<n;b++){
                    if(a==0) matrix[a][b]++;
                    if(b==0) matrix[a][b]++;
                    if(a+1==m) matrix[a][b]++;
                    if(b+1==n) matrix[a][b]++;
                }
            }
            //iterate to N.  
            //F(n)(i,j) = sum(F(n-1) by four neighbor of (i,j))
            //f(i,j,N) = f(i-1,j,N-1)+f(i+1,j,N-1)+f(i,j-1,N-1)+f(i,j+1,N-1)
            int res = matrix[i][j];
            for(int k=1;k<N;k++){
                int[][] next = new int[m][n];
                for(int a=0;a<m;a++){
                    for(int b=0;b<n;b++){
                        if(a>0) next[a][b] = (next[a][b] + matrix[a-1][b])%1000000007;
                        if(b>0) next[a][b] = (next[a][b] + matrix[a][b-1])%1000000007;
                        if(a+1<m) next[a][b] = (next[a][b] + matrix[a+1][b])%1000000007;
                        if(b+1<n) next[a][b] = (next[a][b] + matrix[a][b+1])%1000000007;
                    }
                }
                matrix = next;
                res = (res + matrix[i][j])%1000000007;
            }
            return res;
        }
    }
    

  • 0
    E

    Genius! How did you come up with this idea?


Log in to reply
 

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