मान लीजिए कि एक भूलभुलैया में खाली जगह और दीवारों के साथ एक गेंद है। अब गेंद ऊपर, नीचे, बाएँ या दाएँ किसी भी दिशा में लुढ़क कर खाली रास्तों से जा सकती है, लेकिन दीवार से टकराने तक यह लुढ़कना बंद नहीं करेगी। जब गेंद रुकती है, तो वह अगली दिशा चुन सकती है।
हमें गेंद, गंतव्य और भूलभुलैया की स्थिति शुरू करनी होगी, हमें गेंद को गंतव्य पर रुकने के लिए सबसे छोटी दूरी का पता लगाना होगा। यहां दूरी वास्तव में खाली कोशिकाओं की संख्या से परिभाषित होती है, जो गेंद द्वारा कवर की जाती हैं (प्रारंभ स्थिति को छोड़कर, प्रारंभिक स्थिति सहित)। यदि गेंद को गंतव्य पर रोकना असंभव है, तो वापसी -1.
भूलभुलैया को एक 2डी सरणी द्वारा दर्शाया जाता है। यहां 1 दीवार को इंगित करता है और 0 खाली स्थान को इंगित करता है। भूलभुलैया की सीमाएँ सभी दीवारें हैं। प्रारंभ और गंतव्य निर्देशांक पंक्ति और स्तंभ सूचकांकों द्वारा दर्शाए जाते हैं।
इसलिए, यदि इनपुट एक 2D सरणी द्वारा दर्शाए गए भूलभुलैया की तरह है
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
प्रारंभ स्थिति (0, 4) गंतव्य स्थिति है (4, 4), तो आउटपुट 12 होगा, एक संभावित तरीका है:बाएं से नीचे बाएं से नीचे दाएं से नीचे दाएं। (1+1+3+1+2+2+2) =12
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=पंक्ति गणना, m :=स्तंभ गणना
-
रिट:=अनंत
-
क्रम n x m के एक 2D सरणी को परिभाषित करें
-
एक कतार को परिभाषित करें q
-
q में प्रारंभ डालें
-
जिला [शुरू [0], प्रारंभ [1]]:=0
-
जबकि (नहीं q खाली है), करें -
-
curr :=q का पहला तत्व
-
q से तत्व हटाएं
-
x :=curr[0], y :=curr[1]
-
यदि x गंतव्य के समान है[0] और y गंतव्य के समान है[1], तो -
-
रिट :=न्यूनतम रिट और डिस्ट[x, y]
-
-
currDist :=dist[x, y]
-
tempDist:=0
-
मैं :=x
-
जबकि (i + 1
-
(मैं 1 से बढ़ाइए)
-
(tempDist को 1 से बढ़ाएं)
-
-
अगर currDist + tempDist
-
जिला [i, y] :=currDist + tempDist
-
q में { i, y } डालें
-
-
मैं :=x
-
tempDist:=0
-
जबकि (i - 1>=0 और ग्रिड[i - 1, y] शून्य है), करें -
-
(tempDist को 1 से बढ़ाएं)
-
(i 1 से घटाएं)
-
-
अगर currDist + tempDist *lt; जिला [i, y], फिर -
-
जिला [i, y] :=currDist + tempDist
-
q में { i, y } डालें
-
-
मैं :=y
-
tempDist:=0
-
जबकि (i - 1>=0 और ग्रिड[x, i - 1] शून्य है), करें -
-
(i 1 से घटाएं)
-
(tempDist को 1 से बढ़ाएं)
-
-
अगर currDist + tempDist
-
जिला [एक्स, आई]:=currDist + tempDist
-
q में { x, i } डालें
-
-
मैं :=y
-
tempDist:=0
-
जबकि (i + 1
-
(मैं 1 से बढ़ाइए)
-
(tempDist को 1 से बढ़ाएं)
-
-
अगर currDist + tempDist
-
जिला [एक्स, आई]:=currDist + tempDist
-
q में { x, i } डालें
-
-
-
वापसी (यदि रिट inf के समान है, तो -1, अन्यथा रिट)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestDistance(vector<vector<int<>& grid, vector<int<& start, vector<int<& destination) {
int n = grid.size();
int m = n? grid[0].size() : 0;
int ret = INT_MAX;
vector < vector <int< > dist(n, vector <int<(m, INT_MAX));
queue < vector <int< > q;
q.push(start);
dist[start[0]][start[1]] = 0;
while(!q.empty()){
vector <int< curr = q.front();
q.pop();
int x = curr[0];
int y = curr[1];
if(x == destination[0] && y == destination[1]){
ret = min(ret, dist[x][y]);
}
int currDist = dist[x][y];
int tempDist = 0;
int i = x;
while(i + 1 < n && !grid[i + 1][y]){
i++;
tempDist++;
}
if(currDist + tempDist < dist[i][y]){
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
i = x;
tempDist = 0;
while(i - 1 >= 0 && !grid[i - 1][y]){
tempDist++;
i--;
}
if(currDist + tempDist < dist[i][y]){
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
i = y;
tempDist = 0;
while(i - 1 >= 0 && !grid[x][i - 1]){
i--;
tempDist++;
}
if(currDist + tempDist < dist[x][i]){
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
i = y;
tempDist = 0;
while(i + 1 < m && !grid[x][i + 1]){
i++;
tempDist++;
}
if(currDist + tempDist < dist[x][i]){
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
}
return ret == INT_MAX ? - 1 : ret;
};
main(){
Solution ob;
vector<vector<int<> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
vector<int< v1 = {0,4}, v2 = {4,4};
cout << (ob.shortestDistance(v, v1, v2));
} इनपुट
{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4},{4,4} आउटपुट
12
