मान लीजिए हम एक खाली जमीन पर घर बनाना चाहते हैं जो सभी इमारतों तक सबसे कम दूरी में पहुंचे। हम केवल चार दिशाओं में चल सकते हैं जैसे ऊपर, नीचे, बाएं और दाएं। हमारे पास 0, 1 या 2 के मानों का एक 2D ग्रिड है, जहां −
0 एक खाली जमीन दर्शाता है जिससे हम 자유롭게 गुजर सकते हैं।
1 एक इमारत दर्शाता है जिससे हम गुजर नहीं सकते।
2 एक बाधा दर्शाता है जिससे हम गुजर नहीं सकते।
तो, यदि इनपुट इस तरह है
| 1 | 0 | 2 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
तो आउटपुट 7 होगा क्योंकि दिए गए तीन इमारतें (0,0), (0,4), (2,2) पर मौजूद हैं, और एक बाधा (0,2) पर है तो बिंदु (1,2) घर बनाने के लिए एक आदर्श खाली जमीन है, क्योंकि कुल यात्रा दूरी 3+3+1=7 न्यूनतम है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
ret := inf
n := ग्रिड का पंक्ति आकार
m := ग्रिड का स्तंभ आकार
numberOfOnes := 0
आकार n x m का एक 2D ऐरे dist परिभाषित करें
आकार n x m का एक 2D ऐरे reach परिभाषित करें
i := 0 से आरंभ करें, जब i < n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j < m, अद्यतन करें (j को 1 से बढ़ाएं), करें −
यदि grid[i, j] 1 के समान है, तो −
(numberOfOnes को 1 से बढ़ाएं)
एक कतार q परिभाषित करें
{i, j} को q में डालें
एक सेट visited परिभाषित करें
lvl := 1 से आरंभ करें, जब q खाली नहीं है, अद्यतन करें (lvl को 1 से बढ़ाएं), करें −
sz := q का आकार
जब तक sz शून्येतर है, प्रत्येक पुनरावृत्ति में sz घटाएं, करें −
curr := q का पहला तत्व
q से तत्व हटाएं
x := curr.first
y := curr.second
k := 0 से आरंभ करें, जब k < 4, अद्यतन करें (k को 1 से बढ़ाएं), करें −
nx := x + dir[k, 0]
ny := y + dir[k, 1]
यदि nx और ny ग्रिड की सीमा में हैं या grid[nx,ny] 0 नहीं है, तो
निम्नलिखित भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
{nx, ny} को visited में डालें
dist[nx, ny] := dist[nx, ny] + lvl
(reach[nx, ny] को 1 से बढ़ाएं)
{nx, ny} को q में डालें
i := 0 से आरंभ करें, जब i < n, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j < m, अद्यतन करें (j को 1 से बढ़ाएं), करें −
यदि grid[i, j] 0 के समान है और reach[i, j] numberOfOnes के समान है, तो −
ret := ret और dist[i, j] का न्यूनतम
लौटाएं (यदि ret, inf के समान है, तो -1, अन्यथा ret)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public: int shortestDistance(vector<vector<int>>& grid) { int ret = INT_MAX; int n = grid.size(); int m = grid[0].size(); int numberOfOnes = 0; vector < vector <int> > dist(n, vector <int>(m)); vector < vector <int> > reach(n, vector <int>(m)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == 1){ numberOfOnes++; queue < pair <int, int> > q; q.push({i, j}); set < pair <int, int> > visited; 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 k = 0; k < 4; k++){ int nx = x + dir[k][0]; int ny = y + dir[k][1]; if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue; visited.insert({nx, ny}); dist[nx][ny] += lvl; reach[nx][ny]++; q.push({nx, ny}); } } } } } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){ ret = min(ret, dist[i][j]); } } } return ret == INT_MAX ? -1 : ret; } };इनपुट
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
आउटपुट
7
