在C ++中畅游水中

假设我们有一个N x N网格，每个正方形网格[i] [j]表示该点(i,j)的高程。现在考虑开始下雨了。在时间t，到处的水深为t。当两个正方形的标高分别为t时，我们可以从一个正方形游向另一个4向相邻的正方形。我们可以在零时间内游泳无限距离。

我们应该从位置(0,0)开始。我们必须找到最少的时间才能到达右下角的方块(N-1,N-1)

所以如果输入像

正确的方法是彩色的。因此答案将是16。

为了解决这个问题，我们将遵循以下步骤-

• 定义数据，这将采用三个参数，例如时间x和y。

• 定义大小为4 x 2的数组目录：= {{{1，0}，{-1，0}，{0，1}，{0，-1}}

• n：=网格行，m：=网格列

• 定义优先级队列q

• 定义一个访问过的大小为nxm的2D数组，并用0填充

• 造访过[0，0]：= 1

• 将Data（grid [0，0]，0，0）插入q

• 当（不是q为空）时，执行-

• nx：= dir [i，0] + x，ny：= dir [i，1] + y

• 如果nx> = 0且nx <n和ny> = 0且ny <m且未访问[nx，ny]，则-

• 造访过[nx，y]：= 1

• 将Data（grid [nx，ny]和时间，nx，ny的最大值）插入q

• 返回时间

• node = q的顶部元素，并从q删除元素

• 时间：=节点时间

• x：= x的节点，y：= y的节点

• 如果x与n-1相同且y与m-1相同，则-

• 对于初始化i：= 0，当i <4时，更新（将i增加1），请执行-

• 返回-1

让我们看下面的实现以更好地理解-

示例

#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