Unique Paths II - หาเส้นทางที่ไม่ซ้ำกันพร้อมอุปสรรคใน C++

ภาพรวมปัญหา

หุ่นยนต์อยู่มุมซ้ายบนของกริด n×m เคลื่อนที่ได้แค่ขวาหรือลง บางเซลล์เป็นอุปสรรค (1) หาจำนวนเส้นทางที่ไม่ซ้ำไปมุมขวาล่าง

ตัวอย่าง

Grid: [[0,0,0],[0,1,0],[0,0,0]] → Output: 2

เส้นทาง: Right→Right→Down→Down และ Down→Down→Right→Right

อัลกอริทึม (DP Bottom-up)

1. ถ้าจุดสิ้นสุดเป็นอุปสรรค → return 0
2. สร้างตาราง DP ขนาด a×b
3. เติมแถวสุดท้ายและคอลัมน์สุดท้าย (หยุดเมื่อเจออุปสรรค)
4. เติมส่วนกลาง: dp[i][j] = (obstacleGrid[i][j]==0) ? dp[i+1][j] + dp[i][j+1] : 0
5. return dp[0][0]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int a = obstacleGrid.size();
        int b = obstacleGrid[0].size();
        if(!a || !b) return 0;
        if(obstacleGrid[a-1][b-1]) return 0;
        vector < vector <lli> > dp(a, vector <lli>(b));
        for(int i = b-1; i >= 0; i--) if(obstacleGrid[a-1][i]) break; else dp[a-1][i] = 1;
        for(int i = a-1; i >= 0; i--) if(obstacleGrid[i][b-1]) break; else dp[i][b-1] = 1;
        for(int i = a-2; i >= 0; i--)
            for(int j = b-2; j >= 0; j--)
                dp[i][j] = !obstacleGrid[i][j] ? dp[i+1][j] + dp[i][j+1] : 0;
        return dp[0][0];
    }
};

int main(){
    Solution ob;
    vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
    cout << ob.uniquePathsWithObstacles(v);
}

Input / Output

Input:  [[0,0,0],[0,1,0],[0,0,0]]
Output: 2