C++ में दीवारें और गेट - BFS से निकटतम गेट की दूरी

समस्या विवरण

मान लीजिए हमारे पास एक m x n 2D ग्रिड है, जिसे इन तीन संभावित मानों से इनिशियलाइज़ किया गया है:

• -1 दीवार या बाधा के लिए
• 0 गेट के लिए
• INF अनंत के लिए अर्थात खाली कमरा

यहां 2^31 - 1 = 2147483647 INF है क्योंकि हम मान सकते हैं कि गेट की दूरी 2147483647 से कम है। प्रत्येक खाली कमरे को उसके निकटतम गेट की दूरी से भरें। यदि गेट तक पहुंचना असंभव है, तो इसे INF से भरें।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट होगा:

समाधान दृष्टिकोण

मल्टी-सोर्स BFS (सभी गेट्स से एक साथ शुरू):

1. आकार 4x2 की सरणी dir परिभाषित करें: {{1,0}, {-1,0}, {0,1}, {0,-1}}
2. n := rooms का आकार, m := स्तंभ संख्या
3. पेयर्स की कतार q परिभाषित करें
4. सभी सेल्स के लिए: यदि rooms[i][j] == 0, तो {i, j} को q में डालें
5. lvl := 1 से शुरू करके जब तक q खाली न हो:
   • sz := q का आकार
   • sz बार:
     • curr := q का पहला तत्व, q से हटाएं
     • x := curr.first, y := curr.second
     • 4 दिशाओं के लिए:
       • nx := x + dir[i][0], ny := y + dir[i][1]
       • यदि सीमा से बाहर या rooms[nx][ny] < lvl, तो जारी रखें
       • rooms[nx][ny] := lvl
       • {nx, ny} को q में डालें

C++ कार्यान्वयन

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

void print_vector(vector<vector<auto> > 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, ],]