Chương trình tìm lượng mưa đọng giữa các thung lũng trong C++

Giả sử ta có ma trận 2D, các phần tử đại diện cho độ cao địa hình. Hãy tưởng tượng trời mưa và các khoảng trũng được lấp đầy nước. Ta phải tính lượng mưa bị giữ lại giữa các thung lũng.

Ví dụ ma trận:

Đầu ra = 3, vì có thể giữ 3 đơn vị nước giữa ô 4 và 5.

Để giải quyết, ta dùng priority queue (min-heap) bắt đầu từ các ô biên:

• Định nghĩa struct Data {x, y, h}.
• Priority queue pq sắp xếp theo h tăng dần.
• n = số hàng, nếu n==0 trả 0.
• m = số cột.
• Set visited lưu các ô đã thăm.
• Đưa tất cả ô biên vào pq và visited.
• ret=0, maxVal=0.
• while pq không rỗng:
  • Lấy phần tử có h nhỏ nhất (temp).
  • maxVal = max(maxVal, temp.h).
  • Xét 4 hàng xóm (nx,ny) của (temp.x, temp.y).
  • Nếu (nx,ny) hợp lệ và chưa thăm:
    • val = h[nx][ny].
    • Nếu val < maxVal: ret += maxVal - val; val = maxVal.
    • Đưa (val, nx, ny) vào pq, đánh dấu visited.
• Trả về ret.

Ví dụ

Xem triển khai dưới đây:

#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