Unique Paths II

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

C++:
01 int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
02         int n=obstacleGrid.size();
03         if(n==0)
04             return 0;
05         int m=obstacleGrid[0].size();
06         if(m==0)
07             return 0;
08         if(obstacleGrid[n1][m1]==1)
09             return 0;
10         int A[n][m];
11         for(int i=0;i<n;i++){
12             for(int j=0;j<m;j++)
13                 A[i][j]=0;
14         }
15         A[n1][m1]=1;
16         for(int i=n2;i>=0;i){
17             if((A[i+1][m1]==1)&&(obstacleGrid[i][m1]!=1))
18                 A[i][m1]=1;
19         }
20         for(int i=m2;i>=0;i){
21             if((A[n1][i+1]==1)&&(obstacleGrid[n1][i]!=1))
22                 A[n1][i]=1;
23         }
24         for(int i=n2;i>=0;i){
25             for(int j=m2;j>=0;j){
26                 if(obstacleGrid[i][j]==1)
27                     A[i][j]=0;
28                 else{
29                     A[i][j]=A[i+1][j]+A[i][j+1];
30                 }
31             }
32         }
33         return A[0][0];
34 }
Advertisements
This entry was posted in Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s