C++のユニークパスIII

• 正方形の1は出発点です。開始する正方形は1つだけです。

• 正方形の2は終点です。終了する正方形は1つだけです。

• 正方形の0は空の正方形を表し、上を歩くことができます。

• 正方形-1で、歩くことができない障害物の場合。

障害物のないすべての正方形を1回だけ歩く、開始正方形から終了正方形までの4方向の歩行の数を見つける必要があります。

したがって、入力が-

（0,0）、（0,1）、（0,2）、（0,3）、（1,3）、（1,2）、の2つのパスがあるため、出力は2になります。 （1,1）、（1,0）、（2,0）、（2,1）、（2,2）および（0,0）、（1,0）、（2,0）、（2 、1）、（1,1）、（0,1）、（0,2）、（0,3）、（1,3）、（1,2）、（2,2）。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これには、1つの2D配列グリッドi、j、ex、ey、empty、

  が必要です。

• グリッドの範囲内にないi、jまたはgrid [i、j]が-1と同じ場合、-

  • 0を返す

• grid [i、j]が2と同じ場合、

  • 空が-1の場合はtrueを返します

• x：=0

• （空を1つ減らします）

• grid [i、j]：=-1

• 初期化k：=0の場合、k <4の場合、更新（kを1増やします）、実行-

  • nx：=i + dir [k、0]

  • ny：=j + dir [k、1]

  • x：=x + dfs（grid、nx、ny、ex、ey、empty）

• （空を1増やします）

• grid [i、j]：=0

• xを返す

• メソッドから次のようにします-

• 空：=0

• n：=行数、m：=列数

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • grid [i、j]が0と同じ場合、

      • （空を1増やします）

    • それ以外の場合、grid [i、j]が1と同じ場合、-

      • sx：=i、sy：=j

    • それ以外の場合、grid [i、j]が2と同じ場合、-

      • ex：=i、ey：=j

• dfs（grid、sx、sy、ex、ey、empty）を返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
   public:
   int dfs(vector<vector<int> >& grid, int i, int j, int ex, int ey,
   int empty){
      if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0
      || grid[i][j] == -1)
      return 0;
      if (grid[i][j] == 2) {
         return empty == -1;
      }
      int x = 0;
      empty--;
      grid[i][j] = -1;
      for (int k = 0; k < 4; k++) {
         int nx = i + dir[k][0];
         int ny = j + dir[k][1];
         x += dfs(grid, nx, ny, ex, ey, empty);
      }
      empty++;
      grid[i][j] = 0;
      return x;
   }
   int uniquePathsIII(vector<vector<int> >& grid){
      int empty = 0;
      int sx, sy, ex, ey;
      int n = grid.size();
      int m = grid[0].size();
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (grid[i][j] == 0)
            empty++;
            else if (grid[i][j] == 1) {
               sx = i;
               sy = j;
            }
            else if (grid[i][j] == 2) {
               ex = i;
               ey = j;
            }
         }
      }
      return dfs(grid, sx, sy, ex, ey, empty);
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
   cout << (ob.uniquePathsIII(v));
}

入力

{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}

出力

2