किसी दिए गए मैट्रिक्स में, तत्व की स्थिति का विश्लेषण करने के लिए चार ऑब्जेक्ट हैं:बाएँ, दाएँ, नीचे और ऊपर।
Breadth First Search किसी दिए गए 2-D मैट्रिक्स के दो तत्वों के बीच सबसे छोटी दूरी खोजने के अलावा और कुछ नहीं है। इस प्रकार प्रत्येक सेल में चार ऑपरेशन होते हैं जिन्हें हम चार अंकों में व्यक्त कर सकते हैं जैसे कि,
- '2' वर्णन करता है कि मैट्रिक्स में सेल स्रोत है।
- '3' वर्णन करता है कि मैट्रिक्स में सेल गंतव्य है।
- '1' वर्णन करता है कि सेल को एक दिशा में आगे ले जाया जा सकता है।
- '0' वर्णन करता है कि मैट्रिक्स में सेल को किसी भी दिशा में नहीं ले जाया जा सकता है।
एडोब औचित्य के आधार पर, हम किसी दिए गए मैट्रिक्स पर एक चौड़ाई पहले खोज ऑपरेशन कर सकते हैं।
इस समस्या को हल करने का तरीका
संपूर्ण मैट्रिक्स को पार करने और BFS का उपयोग करके किसी भी सेल के बीच न्यूनतम या सबसे छोटी दूरी खोजने के लिए एल्गोरिथ्म इस प्रकार है:
- सबसे पहले इनपुट रो और कॉलम लें।
- दी गई पंक्ति और स्तंभ के साथ एक मैट्रिक्स प्रारंभ करें।
- एक पूर्णांक फ़ंक्शन shortestDist(int row, int col, int mat[][col]) इनपुट के रूप में रो, कॉलम और मैट्रिक्स को लेता है और मैट्रिक्स के तत्वों के बीच सबसे कम दूरी लौटाता है।
- स्रोत के साथ-साथ गंतव्य तत्व का पता लगाने के लिए चर स्रोत और गंतव्य को प्रारंभ करें।
- यदि तत्व '3' है, तो इसे गंतव्य के रूप में चिह्नित करें और यदि तत्व '2' है, तो इसे स्रोत तत्व के रूप में चिह्नित करें।
- अब दिए गए मैट्रिक्स पर ब्रेडथ फर्स्ट सर्च को लागू करने के लिए क्यू डेटा संरचना को इनिशियलाइज़ करें।
- मैट्रिक्स की पंक्ति और स्तंभ को कतार में जोड़े के रूप में सम्मिलित करें। अब सेल में घूमें और पता करें कि यह डेस्टिनेशन सेल है या नहीं। यदि गंतव्य सेल की दूरी वर्तमान सेल से न्यूनतम या कम है, तो दूरी को अपडेट करें।
- वर्तमान सेल से सेल की न्यूनतम दूरी ज्ञात करने के लिए फिर से दूसरी दिशा में जाएं।
- न्यूनतम दूरी को आउटपुट के रूप में लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
int findDistance(int row, int col, int mat[][5]) {
int source_i, source_j, destination_i, destination_j;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (mat[i][j] == 2) {
source_i = i;
source_j = j;
}
if (mat[i][j] == 3) {
destination_i = i;
destination_j = j;
}
}
}
int dist[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++)
dist[i][j] = INT_MAX;
}
// initialise queue to start BFS on matrix
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
// modified BFS by add constraint checks
while (!q.empty()) {
// storing the x co-ordinate or row information of cell
int x = q.front().first;
// storing the y co-ordinate or column information of cell
int y = q.front().second;
// Remove the cell from queue
q.pop();
// If move towards left is allowed or it is the destnation cell
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
// if distance to reach the cell to the left is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y - 1]) {
dist[x][y - 1] = dist[x][y] + 1;
q.push(mkp(x, y - 1));
}
}
// If move towards right is allowed or it is the destination cell
if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
// if distance to reach the cell to the right is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x][y + 1]) {
dist[x][y + 1] = dist[x][y] + 1;
q.push(mkp(x, y + 1));
}
}
// If upward direction is allowed
if (x - 1 >= 0 && (mat[x - 1][y] == 1 || mat[x - 1][y] == 3)) {
if (dist[x][y] + 1 < dist[x - 1][y]) {
dist[x - 1][y] = dist[x][y] + 1;
q.push(mkp(x - 1, y));
}
}
// If downward direction allowed
if (x + 1 < row && (mat[x + 1][y] == 1 || mat[x + 1][y] == 3)) {
// if distance to reach the cell to the down is less than the computed previous path distance, update it
if (dist[x][y] + 1 < dist[x + 1][y]) {
dist[x + 1][y] = dist[x][y] + 1;
q.push(mkp(x + 1, y));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
// initialising number of rows and columns
int row = 5;
int col = 5;
// initialising matrix
int mat[][5] = {
{1, 0, 0, 2, 1},
{1, 0, 1, 1, 1},
{0, 1, 1, 2, 0},
{3, 1, 0, 0, 1},
{1, 1, 0, 0, 1}
};
int answer = findDistance(row, col, mat);
// When source and destination are unreachable
if (answer == INT_MAX)
cout << "No Path Found" << endl;
else {
cout << "The Shortest Distance between Source and Destination is:" << endl;
cout << answer << endl;
}
return 0;
} आउटपुट
The Shortest Distance between Source and Destination is:4