用C ++找出山谷之间要下雨的程序
假设我们有一个2D矩阵，其中的元素表示地形的高度。让我们想象一下下雨天，山谷中的所有空间都被填满的情况。
我们必须找出山谷之间会下的雨量。
所以，如果输入像
那么输出将是3，因为我们可以在4到5平方之间容纳3个单位的水。
在线示例
让我们看下面的实现以更好地理解-
#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