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 class Solution {
02 public:
03     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int m=obstacleGrid.size();
07         if(m==0)
08             return 0;
09         int n=obstacleGrid[0].size();
10         vector<int*> A(m);
11         for(int i=0;i<m;i++)
12         {
13             A[i]=new int[n];
14             for(int j=0;j<n;j++)
15                 A[i][j]=0;
16         }
17         if(obstacleGrid[0][0]==1)
18             return 0;
19         A[0][0]=1;
20         for(int i=1;i<n;i++)
21         {
22             A[0][i]=(A[0][i1]==0)||(obstacleGrid[0][i]==1)?0:1;
23         }
24         for(int i=1;i<m;i++)
25         {
26             A[i][0]=(A[i1][0]==0)||(obstacleGrid[i][0]==1)?0:1;
27         }
28         for(int i=1;(i<n)&&(i<m);i++)
29         {
30             if(obstacleGrid[i][i]==1)
31             {
32                 A[i][i]=0;
33             }
34             else
35             {
36                 A[i][i]=A[i1][i]+A[i][i1];
37             }
38             for(int j=1;i+j<n;j++)
39             {
40                 if(obstacleGrid[i][i+j]==1)
41                     A[i][i+j]=0;
42                 else
43                     A[i][i+j]=A[i1][i+j]+A[i][i+j1];
44             }
45             for(int j=1;i+j<m;j++)
46             {
47                 if(obstacleGrid[i+j][i]==1)
48                     A[i+j][i]=0;
49                 else
50                     A[i+j][i]=A[i+j1][i]+A[i+j][i1];
51             }
52         }
53         return A[m1][n1];
54     }
55 };
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