63. Unique Paths II

Same solution with problem “62. Unique Paths”. The only difference is the initial state.

1:  class Solution {  
2:  public:  
3:    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {  
4:      int rows = obstacleGrid.size();  
5:      if (rows == 0) return 0;  
6:      int cols = obstacleGrid[0].size();  
7:      vector<vector<int>> dp(rows, vector<int>(cols, 0));  
8:      for (int j = 0; j < cols; j++) {  
9:        if (obstacleGrid[0][j] == 1) break;  
10:        dp[0][j] = 1;  
11:      }  
12:      for (int i = 0; i < rows; i++) {  
13:        if (obstacleGrid[i][0] == 1) break;  
14:        dp[i][0] = 1;  
15:      }  
16:      for (int i = 1; i < rows; i++) {  
17:        for (int j = 1; j < cols; j++) {  
18:          if (obstacleGrid[i][j] == 0) {  
19:            dp[i][j] = dp[i-1][j]+dp[i][j-1];  
20:          }  
21:        }  
22:      }  
23:      return dp[rows-1][cols-1];  
24:    }  
25:  };