C++에서 계곡 사이에 잡아야 하는 비의 양을 알아내는 프로그램

<시간/>

요소가 지형의 높이를 나타내는 2D 행렬이 있다고 가정합니다. 비가 와서 계곡의 모든 공간이 채워지는 상황을 상상해 봅시다.

계곡 사이에 끼게 될 비의 양을 알아내야 합니다.

따라서 입력이 다음과 같으면

6	6	6	8
6	4	5	8
6	6	6	6

그러면 4에서 5칸 사이에 3단위의 물을 담을 수 있으므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

x 및 y 좌표와 높이 h를 포함하는 구조 데이터 정의
우선 순위 대기열 pq를 정의하고 높이 값에 따라 정렬된 데이터 항목을 저장합니다.
n :=h의 크기
n이 0이 아닌 경우 -
- 0 반환
m :=h[0]의 크기
방문이라고 하는 한 쌍의 집합을 정의합니다.
initialize i :=0의 경우, i
- pq에 새 데이터(h[i, 0], i, 0) 삽입
- 방문에 {i, 0} 삽입
- pq에 새 데이터(h[i, m - 1], i, m - 1) 삽입
- 방문에 {i, m - 1} 삽입
for initialize i :=1, i
- pq에 새 데이터(h[0, i], 0, i) 삽입
- 방문한 페이지에 {0, i} 삽입
- pq에 새로운 데이터(h[n - 1, i], n - 1, i) 삽입
- {n - 1, i}를 방문
  에 삽입
ret :=0
maxVal :=0
pq가 비어 있지 않은 동안 −
- temp =pq의 최상위 요소
- pq에서 최상위 요소 삭제
- maxVal :=temp 및 maxVal 높이의 최대값
- x :=온도 x
- y :=온도의 y
- initialize i :=0의 경우, i <4일 때 업데이트(i를 1만큼 증가), 수행 -
  - nx :=x + dir[i, 0]
  - ny :=y + dir[i, 1]
  - nx>=0이고 ny>=0이고 nx
    - 발 :=h[nx, ny]
    - val
      - ret :=ret + maxVal - 발
      - val :=maxVal
    - pq에 새로운 데이터(val, nx, ny) 삽입
    - {nx, ny}를 방문
      에 삽입
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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}
};