在C++中模拟涨水游泳

假设我们有一个N x N的网格，每个方格grid[i][j]表示该点(i,j)的海拔高度。现在开始下雨。在t时刻，处处水深为t。当两个相邻方格的海拔高度都小于等于t时，我们可以从一个方格游到另一个与其四方向相邻的方格。我们可以在零时间内游无限远的距离。

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

因此，如果输入如下所示：

01234
242322215
1213151516
1117181920
109876

正确路径已着色。答案将是16。

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

  • 定义数据结构Data，它将包含三个参数：时间、x和y。
  • 定义一个大小为4 x 2的数组dir：= { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }
  • n := 网格的行数，m := 网格的列数
  • 定义优先队列q
  • 定义一个大小为n x m的二维数组visited，并将其全部元素初始化为0
  • visited[0, 0] := 1
  • 将Data(grid[0, 0], 0, 0)插入到q中
  • 当(q不为空)时，执行以下操作：
    • node = q的顶部元素，并从q中删除该元素
    • time := node的时间
    • x := node的x坐标，y := node的y坐标
    • 如果x等于n - 1且y等于m - 1，则：
      • 返回time
    • 对于i从0开始，i < 4，i递增1，执行以下操作：
      • nx := dir[i, 0] + x, ny := dir[i, 1] + y
      • 如果nx >= 0且nx < n且ny >= 0且ny < m且visited[nx, ny]为假，则：
        • visited[nx, ny] := 1
        • 将Data(max(grid[nx, ny], time), nx, ny)插入到q中
  • 返回-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

更新于：2020年6月2日

247 次浏览

开启您的职业生涯

完成课程后获得认证

开始学习
广告