LeetCode 63. Unique Paths II [Medium] [C++] 解題筆記

這題是 62. Unique Paths 的進階題，一樣給定一個 m x n 的 grid map，要我們求從左上走到右下只能往右或往下走的話，總共有幾種走法。但是 grid map 中有些位置可能是obstacle無法通行。

EX:

  [0,0,0]
  [0,1,0]
  [0,0,0]

1 表示障礙物

Ans 2

想法:

    這題基本上作法跟 62. Unique Paths 一樣，用DP的方式去求得方法數，比較不同的是因為這題有障礙物，

所以在更新 DP array 的時候必須判斷左方前一格與上方前一格是否為障礙物若是則該方向方法數為0。

完整程式碼:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty()) { return 0; }
        int up = 0;
        int left = 0;
        int row = obstacleGrid.size();
        int col = obstacleGrid[0].size();
        vector<int> cur(col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (obstacleGrid[i][j]) {
                    cur[j] = 0;
                    continue;
                }
                if (i == 0 && j == 0) {
                    cur[j] = 1;
                    continue;
                }
                up = (i == 0 || obstacleGrid[i-1][j])? 0 : cur[j];
                left = (j == 0 || obstacleGrid[i][j-1])? 0 : cur[j-1];
                cur[j] = up + left;
            }
        }
                
        return cur[col - 1];           
    }
};