C++-এ Walls and Gates: দরজা থেকে খালি ঘরের দূরত্ব পূরণ করা

একটি m x n ২D গ্রিড দেওয়া আছে যেটি তিনটি ভ্যালু দিয়ে ইনিশিয়ালাইজড: -1 (দেওয়াল/বাধা), 0 (গেট/দরজা), INF (খালি ঘর, এখানে 2147483647)। প্রতিটি খালি ঘরে তার নিকটতম গেট থেকে দূরত্ব পূরণ করতে হবে। যদি গেটে পৌঁছানো না যায়, তবে INF রেখে দিন।

উদাহরণ

ইনপুট গ্রিড:

আউটপুট গ্রিড:

সমাধানের পদ্ধতি (Multi-source BFS)

1. ডিরেকশন অ্যারে dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}।
2. সকল গেট (rooms[i][j] == 0) কিউতে পুশ করুন।
3. লেভেল বাই লেভেল BFS চলান (lvl = 1 থেকে শুরু):
   • প্রতি লেভেলে কিউর সব নোড প্রসেস করুন।
   • প্রতি নোডের ৪ দিক চেক করুন।
   • যদি নতুন পজিশন বৈধ হয় (বাউন্ডের ভিতরে, দেওয়াল নয়, এবং rooms[nx][ny] >= lvl), তবে:
     • rooms[nx][ny] = lvl সেট করুন।
     • নতুন পজিশন কিউতে পুশ করুন।
4. BFS শেষ হলে গ্রিড আপডেটেড থাকবে।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int n = rooms.size();
        int m = n ? rooms[0].size() : 0;
        queue<pair<int, int>> q;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rooms[i][j] == 0)
                    q.push({i, j});
            }
        }
        
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                pair<int, int> curr = q.front(); q.pop();
                int x = curr.first;
                int y = curr.second;
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
                        continue;
                    rooms[nx][ny] = lvl;
                    q.push({nx, ny});
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> v = {{2147483647,-1,0,2147483647}, 
                                {2147483647,2147483647,2147483647,-1}, 
                                {2147483647,-1,2147483647,-1}, 
                                {0,-1,2147483647,2147483647}};
    Solution ob;
    ob.wallsAndGates(v);
    print_vector(v);
    return 0;
}

ইনপুট

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1},{2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

আউটপুট

[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]