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} };
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
3