หาปริมาณน้ำฝนที่เก็บได้ระหว่างหุบเขาในเมทริกซ์ 2D (C++)

บทนำ

ในบทช่วยสอนนี้ เราจะคำนวณ ปริมาณน้ำฝนที่เก็บได้ (Trapping Rain Water II) ในเมทริกซ์ 2D ที่แต่ละเซลล์แทนความสูงของภูมิประเทศ

ตัวอย่าง

Matrix 3×4:

อัลกอริทึม: Priority Queue (Min-Heap) + BFS

คล้าย "Trapping Rain Water" 1D แต่ขยายเป็น 2D:

1. เริ่มจาก ขอบเมทริกซ์ (boundary) ใส่ทุกเซลล์ขอบเข้า Min-Heap เรียงตามความสูง
2. Mark ขอบว่า visited
3. Pop เซลล์ความสูงต่ำสุดจาก heap:
   • อัปเดต maxVal = max(maxVal, cell.height) (ระดับน้ำสูงสุดที่สามารถเก็บได้)
   • ตรวจสอบ 4 เพื่อนบ้าน:
     • ถ้ายังไม่ visited และอยู่ในขอบเขต:
     • ถ้าความสูงเพื่อนบ้าน < maxVal → เก็บน้ำได้ maxVal - height
     • Push เพื่อนบ้านเข้า heap ด้วยความสูง = max(ความสูงเดิม, maxVal)
     • Mark visited
4. ทำซ้ำจน heap ว่าง

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int x, y, 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);  // min-heap
    }
};

int dir[4][2] = {{1,0}, {-1,0}, {0,-1}, {0,1}};

class Solution {
public:
    int solve(vector>& h) {
        priority_queue, Comparator> pq;
        int n = h.size();
        if (!n) return 0;
        int m = h[0].size();
        
        set> visited;
        
        // ใส่ขอบทั้ง 4 ด้าน
        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, maxVal = 0;
        while (!pq.empty()) {
            Data temp = pq.top(); pq.pop();
            maxVal = max(temp.h, maxVal);
            int x = temp.x, y = temp.y;
            
            for (int i = 0; i < 4; i++) {
                int 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>& matrix) {
    return (new Solution())->solve(matrix);
}

int main() {
    vector> v = {
        {6, 6, 6, 8},
        {6, 4, 5, 8},
        {6, 6, 6, 6}
    };
    cout << solve(v);
    return 0;
}

ผลลัพธ์

3

ความซับซ้อน

• เวลา: O(mn log(mn)) - เข้า/ออก heap ทุกเซลล์
• พื้นที่: O(mn) - heap + visited set

สรุป

Trapping Rain Water II 3D ใช้ Min-Heap ขยายจากขอบเข้ามาใน ระดับน้ำ = max height ที่เจอมาแล้ว หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ