C++程序:找出山谷之间积水量


假设我们有一个二维矩阵,其中元素代表地形的的高度。让我们想象一下下雨的情况,所有山谷中的空间都被填满了。

我们必须找出山谷之间将积聚多少雨水。

因此,如果输入如下所示

6668
6458
6666

那么输出将为 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

更新于: 2020-12-23

61 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告