मान लीजिए हमारे पास 0 और 1 से बना एक मैट्रिक्स है, हमें प्रत्येक सेल के लिए निकटतम 0 की दूरी ज्ञात करनी है। यहां दो आसन्न सेल के बीच की दूरी 1 है।
उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
तो आउटपुट होगा:
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 2 | 1 |
हल करने की विधि
हम BFS (ब्रेडथ-फर्स्ट सर्च) का उपयोग करेंगे:
- दिशाओं के लिए एक सरणी dir परिभाषित करें: {{1,0}, {-1,0}, {0,-1}, {0,1}}।
- पंक्तियों और स्तंभों की संख्या n, m लें।
- परिणाम मैट्रिक्स ret को अनंत से भरें।
- एक कतार q परिभाषित करें।
- मैट्रिक्स को पार करें: यदि सेल 0 है, तो ret में 0 सेट करें और कतार में डालें।
- स्तर दर स्तर BFS चलाएं: कतार से सेल निकालें, उसके पड़ोसियों की जांच करें, यदि वे सीमा के भीतर हैं और उनकी दूरी वर्तमान स्तर से अधिक है, तो दूरी अपडेट करें और कतार में डालें।
- ret लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int n = matrix.size(); int m = matrix[0].size(); vector < vector <int> > ret(n, vector <int>(m, INT_MAX)); queue < pair <int, int> > q; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(!matrix[i][j]){ ret[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(); for(int k = 0; k < 4; k++){ int nx = curr.first + dir[k][0]; int ny = curr.second + dir[k][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue; ret[nx][ny] = lvl; q.push({nx, ny}); } } } return ret; } }; main(){ Solution ob; vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}}; print_vector(ob.updateMatrix(v)); }
इनपुट
{{0,0,0},{0,1,0},{1,1,1}}
आउटपुट
[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]
