C++의 고유 경로 II

<시간/>

n x m 그리드(n 행 및 m 열)의 왼쪽 상단 모서리에 로봇이 있다고 가정합니다. 로봇은 어느 시점에서든 아래쪽이나 오른쪽으로만 움직일 수 있습니다. 로봇은 그리드의 오른쪽 하단 모서리에 도달하려고 합니다(아래 다이어그램에서 'END로 표시됨).

그리드의 일부 셀이 표시되어 장애물로 간주됩니다. 그렇다면 가능한 고유한 경로가 몇 개나 찾아야 할까요? 예를 들어 그리드가 [[0,0,0],[0,1,0],[0,0,0]]과 같으면 그리드는 아래와 같습니다 -

로보
	옵스
		종료

출력은 2이므로 시작 위치에서 끝 위치까지 도달하는 총 2가지 방법이 있습니다. 이 경로는 -

오른쪽 → 오른쪽 → 아래쪽 → 아래쪽
아래쪽 → 아래쪽 → 오른쪽 → 오른쪽

단계를 살펴보겠습니다 -

a :=행 수, b :=열 수
그리드[a – 1,b - 1]가 0이 아니면 0을 반환합니다.
순서가 a x b이고 이름이 DP인 테이블 하나 생성
for i :=b – 1에서 0까지
- 그리드[a – 1, i]이면 중단, 그렇지 않으면 DP[a – 1, i] :=1
for i :=a – 1에서 0까지
- 그리드[i, b - 1]이면 중단, 그렇지 않으면 DP[i, b – 1] :=1
for i :=a – 2에서 0까지
- j의 경우 :=b – 2에서 0까지
  - DP[i, j] :=grid[i, j]가 0일 때 DP[i + 1, j] + DP[i, j + 1], 그렇지 않으면 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]]