C++で障害物を除去したグリッド内の最短経路

m x nグリッドがあるとします。ここでは、各セルは0または1です。0セルは空で、1はブロックされています。 1つのステップで、空のセルから上、下、左、または右に移動できます。最大でk個の障害物を排除できることを前提として、左上隅のセル（0、0）から右下隅のセル（m-1、n-1）まで歩くための最小ステップ数を見つける必要があります。そのような方法がない場合は、-1を返します。

したがって、入力が次のような場合

kが1の場合、障害物を除去しない最短経路は10であるため、出力は6になります。位置（3,2）で障害物が1つ除去される最短経路は6になります。このような経路は（0,0）になります。 to（0,1）to（0,2）to（1,2）to（2,2）to（3,2）to（4,2）。

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

• 関数ok（）を定義します。これにより、xとyが範囲rとcにあるかどうかがチェックされます

• サイズ50x50x2000のアレイdpを定義します

• x、y、k、および長さが存在する1つのデータ構造を定義します。

• メインの方法から、次のようにします-

• dpをinfで埋めます

• r：=行数、c：=列数

• 1つのキューを定義するq

• ルートと呼ばれるデータオブジェクトを（x =0、y =0、k、長さ=0）で作成します

• ルートをqに挿入

• （qが空ではない）間、-

  • node：=qの最初の要素

  • qから要素を削除

  • x：=node.x、y：=node.y、k：=node.k、length：=node.length

  • xがr-1と同じで、yがc-1と同じである場合、-

    • 戻り長さ

  • （長さを1増やします）

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

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

    • ny：=y + dir [i、1]

    • nxがr-1と同じで、nyがc-1と同じ場合、-

      • 戻り長さ

    • ok（nx、ny、r、c）が真の場合、-

      • grid [nx、ny]が0と同じ場合、-

        • 長さが

          • （x =nx、y =ny、k、length）の新しいデータオブジェクトをqに挿入します

          • dp [nx、ny、k]：=長さ

      • それ以外の場合

        • k>0で長さが

          • （x =nx、y =ny、k =k-1、length）の新しいデータオブジェクトをqに挿入します

          • dp [nx、ny、k]：=長さ

• -1を返す

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

例

#include <bits/stdc++.h>
using namespace std;
int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dp[50][50][2000];
struct Data{
   int x, y, k, length;
   Data(int a, int b, int c, int d){
      x = a;
      y = b;
      k = c;
      length = d;
   }
};
class Solution {
   public:
   void pre(){
      for (int i = 0; i < 50; i++) {
         for (int j = 0; j < 50; j++) {
            for (int k = 0; k < 2000; k++) {
               dp[i][j][k] = INT_MAX;
            }
         }
      }
   }
   bool ok(int x, int y, int r, int c){
      return (x < r && y < c && x >= 0 && y >= 0);
   }
   int shortestPath(vector<vector<int> >& grid, int k){
      pre();
      int r = grid.size();
      int c = grid[0].size();
      queue<Data> q;
      Data root(0, 0, k, 0);
      q.push(root);
      while (!q.empty()) {
         Data node = q.front();
         q.pop();
         int x = node.x;
         int y = node.y;
         int k = node.k;
         int length = node.length;
         if (x == r - 1 && y == c - 1)
         return length;
         length++;
         for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx == r - 1 && ny == c - 1)
            return length;
            if (ok(nx, ny, r, c)) {
               if (grid[nx][ny] == 0) {
                  if (length < dp[nx][ny][k]) {
                     q.push(Data(nx, ny, k, length));
                     dp[nx][ny][k] = length;
                  }
               }
               else {
                  if (k > 0 && length < dp[nx][ny][k]) {
                     q.push(Data(nx, ny, k - 1, length));
                     dp[nx][ny][k] = length;
                  }
               }
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},
   {0,0,0}};
   cout << (ob.shortestPath(v, 1));
}

入力

{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}

出力

6