C++-এ ২D ম্যাট্রিক্সের উপগহন মধ্যে জল বরাদ্দ বের করুন

মান লিজিয়ে একটি ২D ম্যাট্রিক্স আছে যেখানে এলিমেন্টগুলো টেরেনের উচ্চতা উপস্থাপন করে। কল্পনা করুন বৃষ্টি পড়ছে এবং উপগহনগুলো জল سے পূর্ণ হচ্ছে। আমাদের উপগহন giữaে কতটুকু জল জমা হবে তা বের করতে হবে।

যেমন ইনপুট:

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

তবে আউটপুট হবে ৩ কারণ ৪ এবং ৫ এর মধ্যে ৩ ইউনিট জল জমা হয়।

সমাধানের ধাপগুলো:

Data স্ট্রাকচার সংজ্ঞায়িত করুন যাতে x, y কোঅর্ডিনেট এবং উচ্চতা h থাকে
প্রাইরিটি কিউ pq সংজ্ঞায়িত করুন যা Data আইটেমগুলো উচ্চতা অনুযায়ী সর্ট করে রাখে
n := h.size()
যদি n শূন্য হয়, ০ রিটার্ন করুন
m := h[0].size()
visited নামক পেয়ার সেট সংজ্ঞায়িত করুন
বর্ডার সেলগুলো pq-তে डालুন এবং visited-এ মার্ক করুন
ret := 0, maxVal := 0
যখন pq খালি নয়:

temp = pq.top(); pq.pop()
maxVal = max(temp.h, maxVal)
x = temp.x, y = temp.y
৪ দিক দিয়ে নেighbour চেক করুন:

nx, ny ভ্যালিড এবং visited না হলে:

val = h[nx][ny]
যদি val < maxVal, ret += maxVal - val, val = maxVal
Data(val, nx, ny) pq-তে পুশ করুন, visited-এ যোগ করুন

ret রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশন দেখুন:

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

ইনপুট

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