My accepted solution in Java


  • 0
    A

    int[][] ary=obstacleGrid;

    If we want to get the number of different ways that could get to 'Finish'( ary[m-1][n-1] ).

    We should find the number of different ways that could get to ary[m-1-1][n-1] and ary[m-1][n-1-1] .

    When m==1 or n==1 ,and ary doesn't contains 1, the result would be 1.

    so the ary[0][0] to ary[0][n-1] should be 1, and ary[0][0] to ary[m-1][0] should be 1 .(1 means there are one

    ways could get to that position)

    If the ary[i][j] is 1 then no way could get to (i,j) ,so I overwrite the ary[i][j] by 0.(0 means no ways could get

    to (i,j) )

    An instance:

    Given ary             -> init ary[0][] and ary[][0]        -> i=1 to m-1 ; j=1 to n-1; if(ary[i][j]==1) ary[i][j]=0;
                                                                                            else ary[i][j]=ary[i-1][j]+ary[i][j-1];
       0  0  1  0               1  1  0  0                                     1  1  0  0
       0  1  0  0               1                                              1  0  0  0
       0  0  0  0               1                                              1  1  1  1
       0  0  0  0               1                                              1  2  3  4
                                  
    
    
    
    public class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int[][] ary=obstacleGrid;
            int m=ary.length,n=ary[0].length;
            if(ary[0][0]==1 || ary[m-1][n-1]==1 ) return 0;
            ary[0][0]=1;
            for(int i=1;i<n;i++)
            {
                if(ary[0][i]==1)
                {
                    ary[0][i]=0;
                    i++;
                    while(i<n)
                    {
                        ary[0][i]=0;
                        i++;
                    }
                    break;
                }
                else ary[0][i]=1;
            }
            for(int i=1;i<m;i++)
            {
                if(ary[i][0]==1)
                {
                    ary[i][0]=0;
                    i++;
                    while(i<m)
                    {
                        ary[i][0]=0;
                        i++;
                    }
                    break;
                }
                else ary[i][0]=1;
            }
            for(int i=1;i<m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    if(ary[i][j]==0)
                    {
                        ary[i][j]=ary[i-1][j]+ary[i][j-1];  
                    }
                    else
                    {
                        ary[i][j]=0;
                    }
                }
            }
            return ary[m-1][n-1];
        }
    }

Log in to reply
 

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