เส้นทางที่ไม่ซ้ำ II ใน C++

สมมติว่ามีหุ่นยนต์อยู่ที่มุมบนซ้ายของตารางขนาด n x m (แถว n และคอลัมน์ m) หุ่นยนต์สามารถเคลื่อนที่ได้ทั้งด้านล่างหรือด้านขวาเมื่อใดก็ได้ หุ่นยนต์ต้องการไปถึงมุมล่างขวาของตาราง (ทำเครื่องหมาย 'END ในแผนภาพด้านล่าง)

มีการทำเครื่องหมายบางช่องในตาราง ซึ่งจะถือเป็นอุปสรรค ดังนั้นเราต้องค้นหาว่ามีเส้นทางที่ไม่ซ้ำกันกี่เส้นทาง? ตัวอย่างเช่น หากเส้นตารางเป็นแบบ [[0,0,0],[0,1,0],[0,0,0]] เส้นตารางจะเป็นแบบด้านล่าง −

หุ่นยนต์
	Obs
		END

ผลลัพธ์จะเป็น 2 ดังนั้นจึงมีทั้งหมด 2 วิธีในการเข้าถึงจากตำแหน่งเริ่มต้นไปยังตำแหน่งสิ้นสุด เส้นทางเหล่านี้คือ −

ขวา → ขวา → ล่าง → ลง
ลง → ลง → ขวา → ขวา

ให้เราดูขั้นตอน -

a :=จำนวนแถว b :=จำนวนคอลัมน์
ถ้า grid[a – 1,b - 1] ไม่ใช่ศูนย์ ให้คืนค่า 0
สร้างตารางที่มีลำดับ x b และชื่อ DP
สำหรับ i :=b – 1 เหลือ 0
- ถ้า grid[a – 1, i], แตก, ไม่เช่นนั้น DP[a – 1, i] :=1
for i :=a – 1 down to 0
- ถ้า grid[i, b - 1] แตก มิฉะนั้น DP[i, b – 1] :=1
for i :=a – 2 down to 0
- สำหรับ j :=b – 2 เหลือ 0
  - DP[i, j] :=DP[i + 1, j] + DP[i, j + 1] เมื่อ grid[i, j] เป็น 0 มิฉะนั้น 0
คืน DP[0, 0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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];
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{0,0,0}};
   cout << ob.uniquePathsWithObstacles(v);
}

อินพุต

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