C++で谷間で捕らえられる雨の量を見つけるためのプログラム

要素が地形の高さを表す2Dマトリックスがあるとします。雨が降り、谷のすべてのスペースがいっぱいになる状況を想像してみましょう。

谷間で降る雨の量を調べる必要があります。

したがって、入力が次のような場合

その場合、4〜5個の正方形の間に3単位の水を保持できるため、出力は3になります。

これを解決するには、次の手順に従います-

• x座標とy座標および高さhを含む構造データを定義します

• 優先度付きキューpqを定義し、高さの値で並べ替えられたデータ項目を格納します

• n：=hのサイズ

• nがゼロ以外の場合、-

  • 0を返す

• m：=h [0]

  のサイズ

• 訪問済みと呼ばれるペアの1つのセットを定義します

• 初期化i：=0の場合、i

  • 新しいデータ（h [i、0]、i、0）をpqに挿入します

  • {i、0}をvisited

    に挿入します

  • 新しいデータ（h [i、m-1]、i、m-1）をpqに挿入します

  • {i、m-1}をvisitedに挿入

• 初期化i：=1の場合、i

  • 新しいData（h [0、i]、0、i）をpqに挿入します

  • {0、i}をvisitedに挿入

  • 新しいデータ（h [n-1、i]、n-1、i）をpqに挿入します

  • {n-1、i}をvisited

    に挿入します

• ret：=0

• maxVal：=0

• pqが空でないときに、-

  を実行します。

  • temp=pqの最上位要素

  • pqから最上位の要素を削除します

  • maxVal：=tempとmaxValの高さの最大値

  • x：=xの温度

  • y：=温度のy

  • 初期化i：=0の場合、i <4の場合、更新（iを1増やします）、実行-

    • nx：=x + dir [i、0]

    • ny：=y + dir [i、1]

    • nx> =0かつny>=0かつnx

      • val：=h [nx、ny]

      • val

        • ret：=ret + maxVal --val

        • val：=maxVal

      • 新しいデータ（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