Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में घाटियों के बीच फंसे बारिश के पानी की मात्रा ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास एक 2D मैट्रिक्स है, जहां एलिमेंट्स टेरेन (terrain) की ऊंचाई दर्शाते हैं। आइए एक स्थिति की कल्पना करें जहां बारिश होगी और घाटियों (valleys) में सभी जगह पानी से भर जाएंगी।

हमें घाटियों के बीच फंसे बारिश के पानी की मात्रा ढूंढनी है।

तो, यदि इनपुट है:

6668
6458
6666

तो आउटपुट 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)) है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम C++ में रेखा का मध्य बिंदु खोजने का प्रोग्राम

    इस समस्या में, हमें दो बिंदु A और B दिए गए हैं, एक रेखा के प्रारंभिक और अंतिम बिंदु। हमारा कार्य C++ में रेखा का मध्य बिंदु खोजने के लिए एक प्रोग्राम बनाना है। समस्या विवरण यहां, हमारे पास प्रारंभिक और अंतिम बिंदु A(x1, y1) और B(x2, y2) वाली एक रेखा है। और हमें रेखा का मध्य बिंदु ज्ञात करना है। उद

  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ