इस समस्या में, हमें एक मैट्रिक्स mat[][] दिया गया है। यह लैंडमाइन्स वाले पथ को परिभाषित करता है जिन्हें 0 के रूप में चिह्नित किया गया है। हमारा कार्य लैंडमाइन्स वाले पथ में सबसे छोटा सुरक्षित मार्ग खोजना है।
सुरक्षित पथ से गुजरते समय, हमें लैंडमाइन के आसन्न सेल्स (बाएं, दाएं, ऊपर और नीचे) पर चलने से बचने की आवश्यकता है क्योंकि वे असुरक्षित हैं।
पथ को ट्रैवर्स करते समय सभी वैध चालें हैं -
- बाएं: mat[i][j] => mat[i-1][j] - दाएं: mat[i][j] => mat[i+1][j] - ऊपर: mat[i][j] => mat[i][j - 1] - नीचे: mat[i][j] => mat[i][j + 1]
आइए एक उदाहरण से इस समस्या को समझते हैं,
इनपुट
mat[][] = { {1, 1, 0, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}, {1, 1, 1, 1} }आउटपुट
length of shortest safe path is 7
व्याख्या
{ {1, 1, 0, 1}, {1, 1, 0, 1}, {1, 1, 1, 1}, {1, 1, 1, 1} }समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान बैकट्रैकिंग का उपयोग करना है। लेकिन समाधान के लिए पथ खोजने से पहले, हम उन सभी सेल्स को असुरक्षित सेल्स के रूप में चिह्नित करेंगे जो लैंडमाइन के आसन्न हैं। अब, पहले कॉलम में शुरुआती सेल्स के लिए, हम उस स्थिति से प्रत्येक सुरक्षित सेल पर जाएंगे और फिर जांचेंगे कि क्या यह गंतव्य (अंतिम कॉलम में कोई भी सेल) की ओर ले जाता है या नहीं। फिर उन सभी सुरक्षित स्थितियों के लिए जो गंतव्य तक ले जा सकती हैं, गंतव्य तक पहुंचने के लिए सबसे छोटा पथ ढूंढें। यदि संभव हो, तो पथ की लंबाई वापस करें। अन्यथा -1 वापस करें, जो कोई पथ नहीं मिला को दर्शाता है।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h> using namespace std; #define R 11 #define C 10 int rowNum[] = { -1, 0, 0, 1 }; int colNum[] = { 0, -1, 1, 0 }; bool isSafe(int mat[R][C], int isvisited[R][C], int x, int y){ if (mat[x][y] == 0 || isvisited[x][y]) return false; return true; } bool isValid(int x, int y){ if (x < R && y < C && x >= 0 && y >= 0) return true; return false; } void unSafeCellsInPath(int mat[R][C]){ for (int i = 0; i < R; i++){ for (int j = 0; j < C; j++){ if (mat[i][j] == 0){ for (int k = 0; k < 4; k++) if (isValid(i + rowNum[k], j + colNum[k])) mat[i + rowNum[k]][j + colNum[k]] = -1; } } } for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++){ if (mat[i][j] == -1) mat[i][j] = 0; } } } void findShortestSafeRouteRec(int mat[R][C], int isvisited[R][C], int i, int j, int &min_dist, int dist){ if (j == C-1){ min_dist = min(dist, min_dist); return; } if (dist > min_dist) return; isvisited[i][j] = 1; for (int k = 0; k < 4; k++){ if (isValid(i + rowNum[k], j + colNum[k]) && isSafe(mat, isvisited, i + rowNum[k], j + colNum[k])){ findShortestSafeRouteRec(mat, isvisited, i + rowNum[k], j + colNum[k], min_dist, dist + 1); } } isvisited[i][j] = 0; } int findShortestSafeRoute(int mat[R][C]){ int minSafeDist = INT_MAX; int isvisited[R][C]; unSafeCellsInPath(mat); for (int i = 0; i < R; i++) { if (mat[i][0] == 1) { memset(isvisited, 0, sizeof isvisited); findShortestSafeRouteRec(mat, isvisited, i, 0, minSafeDist, 0); if(minSafeDist == C - 1) break; } } if (minSafeDist != INT_MAX) return minSafeDist; else return -1; } int main() { int mat[R][C] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 } }; int pathLen = findShortestSafeRoute(mat); if(pathLen == -1) cout<<"No Safe Path from source to destination possible!"; else cout<<"Shortest Safe route Length is "<<pathLen; return 0; }आउटपुट
Shortest Safe route Length is 10
वैकल्पिक समाधान
इस समस्या का एक वैकल्पिक समाधान ब्रेडथ फर्स्ट सर्च का उपयोग करना है। क्यू का उपयोग करके, हम पहले कॉलम से अंतिम कॉलम तक का पथ ढूंढेंगे और फिर पहले कॉलम से अंतिम कॉलम तक पथ के लिए न्यूनतम दूरी वापस करेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h> using namespace std; #define R 11 #define C 10 int rowNum[] = { -1, 0, 0, 1 }; int colNum[] = { 0, -1, 1, 0 }; struct Key{ int x,y; Key(int i,int j){ x=i;y=j;}; }; bool isValid(int x, int y) { if (x < R && y < C && x >= 0 && y >= 0) return true; return false; } int findShortestSafeRoute(int mat[R][C]){ for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (mat[i][j] == 0) { for (int k = 0; k < 4; k++) if (isValid(i + rowNum[k], j + colNum[k])) mat[i + rowNum[k]][j + colNum[k]] = -1; } } } for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (mat[i][j] == -1) mat[i][j] = 0; } } int visited[R][C]; for(int i=0;i<R;i++){ for(int j=0;j<C;j++) visited[i][j] = -1; } queue<Key> distQueue; for(int i=0;i<R;i++){ if(mat[i][0] == 1){ distQueue.push(Key(i,0)); visited[i][0] = 0; } } while(!distQueue.empty()){ Key k = distQueue.front(); distQueue.pop(); int d = visited[k.x][k.y]; int x = k.x; int y = k.y; for (int k = 0; k < 4; k++) { int xp = x + rowNum[k]; int yp = y + colNum[k]; if(isValid(xp,yp) && visited[xp][yp] == -1 && mat[xp][yp] == 1){ visited[xp][yp] = d+1; distQueue.push(Key(xp,yp)); } } } int pathLen = INT_MAX; for(int i=0;i<R;i++){ if(mat[i][C-1] == 1 && visited[i][C-1] != -1){ pathLen = min(pathLen,visited[i][C-1]); } } if(pathLen == INT_MAX) return -1; else return pathLen; } int main() { int mat[R][C] = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 } }; int pathLen = findShortestSafeRoute(mat); if(pathLen == -1) cout<<"No Safe Path from source to destination possible!"; else cout<<"Shortest Safe route Length is "<<pathLen; return 0; }आउटपुट
Shortest Safe route Length is 10
