Solution to LeetCode Problems: Unique Paths II

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 3x3 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.

Thoughts:
We cannot use the combination trip anymore. Are we forced to use graph search?
Set the paths to the top-left of the grid, i.e. (0,0) as 1, if not blocked. Then any point in the grid has the number fo unique paths:

1. if blocked  
2.   0  
3. else  
4.   path_from_left + path_from_top  

So we can simply traverse the grid row by row and fill up the values. Extra memory allocation is not necessary, we can use the original grid.


Solution:

1. class Solution {  
2. public:  
3.     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {  
4.         const size_t RR = obstacleGrid.size();  
5.         const size_t CC = obstacleGrid[0].size();  
6.           
7.         // fill up the grid system  
8.         for(size_t r = 0; r < RR; ++r)  
9.             for(size_t c = 0; c < CC; ++c)  
10.             {  
11.                 if (obstacleGrid[r][c] == 1)  
12.                     // blocked...  
13.                     obstacleGrid[r][c] = 0;  
14.                 else if (r == 0 && c == 0)  
15.                     // starting point  
16.                     obstacleGrid[r][c] = 1;  
17.                 else {  
18.                     int right_ways = (c == 0 ? 0 : obstacleGrid[r][c-1]);  
19.                     int top_ways = (r == 0 ? 0 : obstacleGrid[r-1][c]);  
20.                     obstacleGrid[r][c] = right_ways + top_ways;  
21.                 }  
22.             }  
23.           
24.         return obstacleGrid[RR - 1][CC - 1];  
25.     }  
26. };