Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình tìm ra lượng mưa có thể thu được giữa các thung lũng trong C ++

Giả sử chúng ta có một ma trận 2D, trong đó các phần tử đại diện cho chiều cao của địa hình. Hãy tưởng tượng tình huống trời sẽ mưa và tất cả các khoảng trống trong thung lũng bị lấp đầy.

Chúng ta phải tìm ra lượng mưa sẽ hứng chịu giữa các thung lũng.

Vì vậy, nếu đầu vào giống như

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

thì đầu ra sẽ là 3 vì chúng ta có thể chứa 3 đơn vị nước trong khoảng từ 4 đến 5 hình vuông.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định cấu trúc Dữ liệu, chứa tọa độ x, y và chiều cao h

  • Xác định pq hàng đợi ưu tiên, nó lưu trữ các mục dữ liệu được sắp xếp theo giá trị chiều cao

  • n:=kích thước của h

  • nếu n khác 0 thì -

    • trả về 0

  • m:=kích thước của h [0]

  • Xác định một tập hợp các cặp được gọi là đã truy cập

  • để khởi tạo i:=0, khi i

    • chèn Dữ liệu mới (h [i, 0], i, 0) vào pq

    • chèn {i, 0} vào đã truy cập

    • chèn Dữ liệu mới (h [i, m - 1], i, m - 1) vào pq

    • chèn {i, m - 1} vào đã truy cập

  • để khởi tạo i:=1, khi tôi

    • chèn Dữ liệu mới (h [0, i], 0, i) vào pq

    • chèn {0, i} vào đã truy cập

    • chèn Dữ liệu mới (h [n - 1, i], n - 1, i) vào pq

    • chèn {n - 1, i} vào đã truy cập

  • ret:=0

  • maxVal:=0

  • trong khi pq không trống, hãy làm -

    • temp =phần tử hàng đầu của pq

    • xóa phần tử hàng đầu khỏi pq

    • maxVal:=tối đa chiều cao của nhiệt độ và maxVal

    • x:=x nhiệt độ

    • y:=y của nhiệt độ

    • để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -

      • nx:=x + dir [i, 0]

      • ny:=y + dir [i, 1]

      • nếu nx> =0 và ny> =0 và nx

        • val:=h [nx, ny]

        • nếu val

          • ret:=ret + maxVal - val

          • val:=maxVal

        • chèn Dữ liệu mới (val, nx, ny) vào pq

        • chèn {nx, ny} vào đã truy cập

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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

Đầu vào 

{
   {6, 6, 6, 8},
   {6, 4, 5, 8},
   {6, 6, 6, 6}
};

Đầu ra 

3