एक दिए गए मैट्रिक्स में, एलिमेंट पोजीशन का विश्लेषण करने के लिए चार ऑब्जेक्ट हैं: बाएं, दाएं, नीचे और ऊपर।
ब्रेडथ फर्स्ट सर्च दिए गए 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;
}
// BFS शुरू करने के लिए क्यू इनिशियलाइज़ करें
queue < pair < int, int >> q;
q.push(make_pair(source_i, source_j));
dist[source_i][source_j] = 0;
// कंस्ट्रेंट चेक जोड़कर मॉडिफाइड BFS
while (!q.empty()) {
// सेल की x कोऑर्डिनेट या रो जानकारी स्टोर करना
int x = q.front().first;
// सेल की y कोऑर्डिनेट या कॉलम जानकारी स्टोर करना
int y = q.front().second;
// सेल को क्यू से हटाएं
q.pop();
// यदि बाएं मूव करने की अनुमति है या यह गंतव्य सेल है
if (y - 1 >= 0 && (mat[x][y - 1] == 1 || mat[x][y - 1] == 3)) {
// यदि बाएं सेल तक पहुंचने की दूरी गणना की गई पिछली पथ दूरी से कम है, तो इसे अपडेट करें
if (dist[x][y] + 1 < dist[x][y - 1]) {
dist[x][y - 1] = dist[x][y] + 1;
q.push(make_pair(x, y - 1));
}
}
// यदि दाएं मूव करने की अनुमति है या यह गंतव्य सेल है
if (y + 1 < col && (mat[x][y + 1] == 1 || mat[x][y + 1] == 3)) {
// यदि दाएं सेल तक पहुंचने की दूरी गणना की गई पिछली पथ दूरी से कम है, तो इसे अपडेट करें
if (dist[x][y] + 1 < dist[x][y + 1]) {
dist[x][y + 1] = dist[x][y] + 1;
q.push(make_pair(x, y + 1));
}
}
// यदि ऊपर की दिशा अनुमत है
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(make_pair(x - 1, y));
}
}
// यदि नीचे की दिशा अनुमत है
if (x + 1 < row && (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(make_pair(x + 1, y));
}
}
}
return dist[destination_i][destination_j];
}
int main() {
// रो और कॉलम की संख्या इनिशियलाइज़ करना
int row = 5;
int col = 5;
// मैट्रिक्स इनिशियलाइज़ करना
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);
// जब स्रोत और गंतव्य पहुंच से बाहर हों
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
