C++で上昇する水で泳ぐ

1つのNxNグリッドがあり、各正方形グリッド[i] [j]はそのポイント（i、j）での標高を表しているとします。雨が降り始めたと考えてください。時間tでは、あらゆる場所の水深はtです。両方の正方形の高度が最大でtの場合、正方形から別の4方向に隣接する正方形に泳ぐことができます。ゼロ時間で無限の距離を泳ぐことができます。

位置（0、0）から開始する必要があります。右下の正方形（N-1、N-1）に到達するまでの最短時間を見つける必要があります

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

正しい方法は色分けされています。したがって、答えは16になります。

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

• データを定義します。これには、時間、x、yなどの3つのパラメータが必要です。
• サイズの配列ディレクトリを定義します：4 x 2：={{1、0}、{-1、0}、{0、1}、{0、-1}}
• n：=グリッドの行、m：=グリッドの列
• 優先キューqを定義する
• 訪問したサイズnxmの2D配列を1つ定義し、これに0を入力します
• visited [0、0]：=1
• Data（grid [0、0]、0、0）をqに挿入します
• （qが空ではない）間、-
  を実行します
  • node =qの最上位要素であり、qから要素を削除します
  • time：=ノードの時間
  • x：=ノードのx、y：=ノードのy
  • xがn-1と同じで、yがm-1と同じ場合、-
    • 返却時間
  • iを初期化する場合：=0、i <4の場合、更新（iを1増やす）、実行-
    • nx：=dir [i、0] + x、ny：=dir [i、1] + y
    • nx> =0かつnx=0かつny
    • visited [nx、y]：=1
    • データ（グリッド[nx、ny]と時間、nx、nyの最大値）をqに挿入します

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

例

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int time, x, y;
   Data(int a, int b, int y){
      time = a;
      x = b;
      this->y = y;
   }
};
struct Comparator{
   bool operator()(Data a, Data b){
      return !(a.time < b.time);
   }
};
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int swimInWater(vector<vector<int>>& grid) {
      int n = grid.size();
      int m = grid[0].size();
      priority_queue <Data, vector <Data>, Comparator> q;
      vector < vector <int> > visited(n, vector <int>(m, 0));
      visited[0][0] = 1;
      q.push(Data(grid[0][0], 0, 0));
      while(!q.empty()){
         Data node = q.top();
         q.pop();
         int time = node.time;
         int x = node.x;
         int y = node.y;
         if(x == n - 1 && y == m - 1)return time;
         for(int i = 0; i < 4; i++){
            int nx = dir[i][0] + x;
            int ny = dir[i][1] + y;
            if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]){
               visited[nx][y] = 1;
               q.push(Data(max(grid[nx][ny], time), nx, ny));
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},   {10,9,8,7,6}};
   cout << (ob.swimInWater(v));
}

入力

{{0,1,2,3,4},{24,23,22,21,5},{12,13,15,15,16},{11,17,18,19,20},{10,9,8,7,6}}

出力

16