C++のUniquePathsII

n x mグリッド（n行m列）の左上隅にロボットがあるとします。ロボットは、どの時点でも下側または右側のどちらかにしか移動できません。ロボットはグリッドの右下隅に到達しようとしています（下の図で「END」とマークされています）。

グリッド内の一部のセルがマークされており、障害物と見なされます。では、可能な一意のパスがいくつあるかを見つける必要がありますか？たとえば、グリッドが[[0,0,0]、[0,1,0]、[0,0,0]]のような場合、グリッドは次のようになります-

出力は2になるため、開始位置から終了位置に到達する方法は全部で2つあります。これらのパスは-

1. 右→右→下→下
2. 下→下→右→右

手順を見てみましょう-

• a：=行数、b：=列数
• grid [a – 1、b --1]がゼロ以外の場合、0を返します
• 順序がxbで、名前がDPであるテーブルを1つ作成します
• for i：=b –1から0まで
  • grid [a – 1、i]の場合は中断し、そうでない場合はDP [a – 1、i]：=1
• for i：=a –1から0まで
  • grid [i、b --1]の場合は中断し、そうでない場合はDP [i、b – 1]：=1
• for i：=a –2から0まで
  • for 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]]

出力

2