資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中模擬漲水游泳
假設我們有一個N x N的網格，每個方格grid[i][j]表示該點(i,j)的海拔高度。現在開始下雨。在t時刻，處處水深為t。當兩個相鄰方格的海拔高度都小於等於t時，我們可以從一個方格游到另一個與其四方向相鄰的方格。我們可以在零時間內遊無限遠的距離。
我們應該從位置(0, 0)開始。我們必須找到到達右下方方格(N-1, N-1)的最小時間。
因此，如果輸入如下所示：
| 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。
為了解決這個問題，我們將遵循以下步驟：
- 定義資料結構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 次瀏覽
廣告