在C ++中畅游水中
假设我们有一个NxN网格，每个正方形网格[i][j]表示该点(i,j)的高程。现在考虑开始下雨了。在时间t，到处的水深为t。当两个正方形的标高分别为t时，我们可以从一个正方形游向另一个4向相邻的正方形。我们可以在零时间内游泳无限距离。
我们应该从位置(0,0)开始。我们必须找到最少的时间才能到达右下角的方块(N-1,N-1)
所以如果输入像
24221719正确的方法是彩色的。因此答案将是16。
为了解决这个问题，我们将遵循以下步骤-
定义数据，这将采用三个参数，例如时间x和y。
定义大小为4x2的数组目录：={{{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