C++ में घाटियों के बीच होने वाली वर्षा की मात्रा का पता लगाने के लिए कार्यक्रम

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

हमें यह पता लगाना होगा कि घाटियों के बीच कितनी बारिश होगी।

तो, अगर इनपुट पसंद है

तो आउटपुट 3 होगा क्योंकि हम 4 और 5 वर्गों के बीच में 3 यूनिट पानी रख सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक संरचना डेटा परिभाषित करें, जिसमें x और y समन्वय और ऊंचाई h शामिल हो

• प्राथमिकता कतार pq को परिभाषित करें, यह ऊंचाई मानों पर क्रमबद्ध डेटा आइटम संग्रहीत करता है

• n :=h का आकार

• यदि n शून्येतर है, तो -

  • वापसी 0

• मी :=h का आकार[0]

• जोड़े के एक सेट को परिभाषित करें जिसे विज़िट किया गया कहा जाता है

• इनिशियलाइज़ i:=0 के लिए, जब i

  • pq में नया डेटा (h[i, 0], i, 0) डालें

  • विज़िट किए गए में {i, 0} डालें

  • pq में नया डेटा (h[i, m-1], i, m-1) डालें

  • विज़िट किए गए में {i, m - 1} डालें

• इनिशियलाइज़ i :=1 के लिए, जब i

  • pq में नया डेटा (h[0, i], 0, i) डालें

  • विज़िट किए गए में {0, i} डालें

  • pq में नया डेटा (h[n - 1, i], n-1, i) डालें

  • विज़िट किए गए में {n - 1, i} डालें

• रिट:=0

• मैक्सवैल :=0

• जबकि pq खाली नहीं है, −

  . करें

  • अस्थायी =pq का शीर्ष तत्व

  • pq से शीर्ष तत्व हटाएं

  • maxVal :=अधिकतम तापमान और maxVal की ऊंचाई

  • x :=तापमान का x

  • y:=तापमान का y

  • इनिशियलाइज़ करने के लिए मैं :=0, जब i <4, अपडेट (i 1 से बढ़ाएँ), करें -

    • एनएक्स:=एक्स + डीआईआर [i, 0]

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

    • अगर nx>=0 और ny>=0 और nx

      • वैल:=एच[एनएक्स, एनवाई]

      • अगर वैल <मैक्सवैल, तो -

        • रिट :=रिट + मैक्सवैल - वैल

        • वैल:=मैक्सवैल

      • pq में नया डेटा (वैल, एनएक्स, एनवाई) डालें

      • विज़िट किए गए में {nx, ny} डालें

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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

इनपुट

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

आउटपुट

3