Leetcode 63: Unique Paths II (iterative dp)

leetcode_63b.cpp

#include <iostream>
#include <vector>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int rows = obstacleGrid.size();
    if (rows == 0) return 0;
    int cols = obstacleGrid[0].size();
    if (cols == 0) return 0;
    vector<vector<long>> dp(rows, vector<long>(cols, 0));
    dp[0][0] = (obstacleGrid[0][0] == 1 ? 0 : 1);
    for (int c=1; c<cols; ++c)
        dp[0][c] = (obstacleGrid[0][c] == 1 ? 0 : dp[0][c-1]);
    for (int r=1; r<rows; ++r)
        dp[r][0] = (obstacleGrid[r][0] == 1 ? 0 : dp[r-1][0]);
    for (int r=1; r<rows; ++r) {
        for (int c=1; c<cols; ++c) 
            dp[r][c] = (obstacleGrid[r][c] == 1 ? 0 : dp[r-1][c] + dp[r][c-1]);
    }
    return dp[rows-1][cols-1];
}

int main() {
    vector<vector<int>> obs{{0,0,0},{0,1,0},{0,0,0}}; //{{1}};
    cout << uniquePathsWithObstacles(obs) << "\n";
    return 0;
}