資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：找出山谷之間積水量
假設我們有一個二維矩陣，其中元素代表地形的的高度。讓我們想象一下下雨的情況，所有山谷中的空間都被填滿了。
我們必須找出山谷之間將積聚多少雨水。
因此，如果輸入如下所示
| 6 | 6 | 6 | 8 |
| 6 | 4 | 5 | 8 |
| 6 | 6 | 6 | 6 |
那麼輸出將為 3，因為我們可以在 4 和 5 個方格之間容納 3 個單位的水。
為了解決這個問題，我們將遵循以下步驟 -
定義一個名為 Data 的結構體，其中包含 x 和 y 座標以及高度 h
定義一個優先佇列 pq，它儲存按高度值排序的資料項
n := h 的大小
如果 n 不為零，則 -
返回 0
m := h[0] 的大小
定義一個名為 visited 的鍵值對集合
初始化 i := 0，當 i < n 時，更新 (i 加 1)，執行 -
將新的 Data(h[i, 0], i, 0) 插入到 pq 中
將 {i, 0} 插入到 visited 中
將新的 Data(h[i, m - 1], i, m - 1) 插入到 pq 中
將 {i, m - 1} 插入到 visited 中
初始化 i := 1，當 i < m - 1 時，更新 (i 加 1)，執行 -
將新的 Data(h[0, i], 0, i) 插入到 pq 中
將 {0, i} 插入到 visited 中
將新的 Data(h[n - 1, i], n - 1, i) 插入到 pq 中
將 {n - 1, i} 插入到 visited 中
ret := 0
maxVal := 0
當 pq 不為空時，執行 -
temp = pq 的頂部元素
從 pq 中刪除頂部元素
maxVal := temp 的高度和 maxVal 的最大值
x := temp 的 x
y := temp 的 y
初始化 i := 0，當 i < 4 時，更新 (i 加 1)，執行 -
nx := x + dir[i, 0]
ny := y + dir[i, 1]
如果 nx >= 0 且 ny >= 0 且 nx < n 且 ny < m 且 {nx, ny} 未被訪問，則 -
val := h[nx, ny]
如果 val < maxVal，則 -
ret := ret + maxVal - val
val := maxVal
將新的 Data(val, nx, ny) 插入到 pq 中
將 {nx, ny} 插入到 visited 中
返回 ret
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
struct Data {
int x, y;
int h;
Data(int a, int b, int c) {
h = a;
x = b;
y = c;
}
};
struct Comparator {
bool operator()(Data a, Data b) {
return !(a.h < b.h);
}
};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
int solve(vector<vector<int>>& h) {
priority_queue<Data, vector<Data>, Comparator> pq;
int n = h.size();
if (!n)
return 0;
int m = h[0].size();
set<pair<int, int>> visited;
for (int i = 0; i < n; i++) {
pq.push(Data(h[i][0], i, 0));
visited.insert({i, 0});
pq.push(Data(h[i][m - 1], i, m - 1));
visited.insert({i, m - 1});
}
for (int i = 1; i < m - 1; i++) {
pq.push(Data(h[0][i], 0, i));
visited.insert({0, i});
pq.push(Data(h[n - 1][i], n - 1, i));
visited.insert({n - 1, i});
}
int ret = 0;
int maxVal = 0;
while (!pq.empty()) {
Data temp = pq.top();
pq.pop();
maxVal = max(temp.h, maxVal);
int x = temp.x;
int y = temp.y;
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = x + dir[i][0];
ny = y + dir[i][1];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && !visited.count({nx, ny})) {
int val = h[nx][ny];
if (val < maxVal) {
ret += maxVal - val;
val = maxVal;
}
pq.push(Data(val, nx, ny));
visited.insert({nx, ny});
}
}
}
return ret;
}
};
int solve(vector<vector<int>>& matrix) {
return (new Solution())->solve(matrix);
}
int main(){
vector<vector<int>> v = {
{6, 6, 6, 8},
{6, 4, 5, 8},
{6, 6, 6, 6}
};
cout << solve(v);
}輸入
{
{6, 6, 6, 8},
{6, 4, 5, 8},
{6, 6, 6, 6}
};輸出
3
61 次瀏覽
