C++ উপত্যকার মধ্যে বৃষ্টির পরিমাণ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি 2D ম্যাট্রিক্স আছে, যেখানে উপাদানগুলি একটি ভূখণ্ডের উচ্চতাকে প্রতিনিধিত্ব করে। আসুন এমন একটি পরিস্থিতি কল্পনা করি যেখানে বৃষ্টি হবে এবং উপত্যকার সমস্ত স্থান পূর্ণ হয়ে যাবে।

উপত্যকার মধ্যে যে পরিমাণ বৃষ্টি হবে তা আমাদের খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

৷

6	6	6	8
6	4	5	8
6	6	6	6

তাহলে আউটপুট হবে 3 কারণ আমরা 4 থেকে 5 বর্গক্ষেত্রের মধ্যে 3 ইউনিট জল ধরে রাখতে পারি৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি গঠন ডেটা সংজ্ঞায়িত করুন, যেটিতে x এবং y স্থানাঙ্ক এবং উচ্চতা h
রয়েছে
একটি অগ্রাধিকার সারি pq সংজ্ঞায়িত করুন, এটি উচ্চতার মান অনুসারে সাজানো ডেটা আইটেম সংরক্ষণ করে
n :=h
এর আকার
যদি n অ-শূন্য হয়, তাহলে −
- ফেরত 0
m :=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} ভিজিটেড
  -এ ঢোকান
ret :=0
maxVal :=0
pq খালি না থাকার সময় −
করুন
- temp =pq
  এর শীর্ষ উপাদান
- pq
  থেকে শীর্ষ উপাদান মুছুন
- maxVal :=তাপমাত্রার সর্বোচ্চ উচ্চতা এবং maxVal
- x :=তাপমাত্রার x
- y :=y of temp
- আরম্ভ করার জন্য i :=0, যখন i <4, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
  - nx :=x + dir[i, 0]
  - ny :=y + dir[i, 1]
  - যদি nx>=0 এবং ny>=0 এবং nx
    - val :=h[nx, ny]
    - যদি val
      - ret :=ret + maxVal - val
      - val :=maxVal
    - pq
      -এ নতুন ডেটা (val, nx, ny) সন্নিবেশ করান
    - {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}
};