परिचय
मान लीजिए हमारे पास एक 2D मैट्रिक्स है, जहां एलिमेंट्स टेरेन (terrain) की ऊंचाई दर्शाते हैं। आइए एक स्थिति की कल्पना करें जहां बारिश होगी और घाटियों (valleys) में सभी जगह पानी से भर जाएंगी।
हमें घाटियों के बीच फंसे बारिश के पानी की मात्रा ढूंढनी है।
तो, यदि इनपुट है:
| 6 | 6 | 6 | 8 |
| 6 | 4 | 5 | 8 |
| 6 | 6 | 6 | 6 |
तो आउटपुट 3 होगा क्योंकि हम 4 और 5 वर्गों के बीच 3 यूनिट पानी रोक सकते हैं।
समाधान दृष्टिकोण
प्रायोरिटी क्यू (मिन-हीप) का उपयोग करके बाउंडरी सेल्स से शुरू करें। यह "Trapping Rain Water II" (LeetCode 407) समस्या है। सबसे कम बाउंडरी से शुरू करके अंदर की ओर फैलें, पानी का स्तर ट्रैक करें।
उदाहरण कोड
#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, 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);
return 0;
}
इनपुट
{
{6, 6, 6, 8},
{6, 4, 5, 8},
{6, 6, 6, 6}
};
आउटपुट
3
व्याख्या
बाहरी बाउंडरी न्यूनतम ऊंचाई 6 है। अंदर के सेल्स (1,1)=4 और (1,2)=5 हैं। पानी का स्तर 6 तक बढ़ सकता है। फंसा पानी: (6-4) + (6-5) = 2 + 1 = 3 यूनिट।
निष्कर्ष
यह 2D में "ट्रैपिंग रेन वॉटर" समस्या का क्लासिक समाधान है। मिन-हीप बाउंडरी सेल्स को ऊंचाई के क्रम में प्रोसेस करता है। समय जटिलता O(mn log(mn)) है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।