इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो दिए गए मैट्रिक्स में दो सेल के बीच पथ मौजूद है या नहीं जांचता है।
मान लीजिए हमें एक वर्ग मैट्रिक्स दिया गया है जिसमें संभावित मान 0, 1, 2 और 3 हैं। यहां,
- 0 का अर्थ है खाली दीवार
- 1 का अर्थ है स्रोत
- 2 का अर्थ है गंतव्य
- 3 का अर्थ है खाली सेल
मैट्रिक्स में केवल एक स्रोत और गंतव्य हो सकता है। प्रोग्राम यह देखने के लिए है कि दिए गए मैट्रिक्स में स्रोत से गंतव्य तक सभी चार संभावित दिशाओं में लेकिन विकर्ण रूप से नहीं, कोई संभावित पथ है या नहीं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
// दिए गए एरे से संभावित ग्राफ बनाना
class use_graph {
int W;
list <int> *adj;
public:
use_graph(int W) {
this->W = W;
adj = new list<int>[W];
}
void add_side(int source, int dest);
bool search(int source, int dest);
};
// किनारे जोड़ने का फंक्शन
void use_graph::add_side(int source, int dest) {
adj[source].push_back(dest);
adj[dest].push_back(source);
}
// BFS करने का फंक्शन
bool use_graph::search(int source, int dest) {
if (source == dest)
return true;
// तत्वों को आरंभ करना
bool *visited = new bool[W];
for (int i = 0; i < W; i++)
visited[i] = false;
list<int> queue;
// तत्वों को विजिटेड मार्क करना और कतार से हटाना
visited[source] = true;
queue.push_back(source);
// आसन्न शीर्षों पर जाना
list<int>::iterator i;
while (!queue.empty()) {
source = queue.front();
queue.pop_front();
for(i = adj[source].begin(); i != adj[source].end(); ++i) {
if (*i == dest)
return true;
if (!visited[*i]) {
visited[*i] = true;
queue.push_back(*i);
}
}
}
// यदि गंतव्य तक नहीं पहुंचा
return false;
}
bool is_okay(int i, int j, int M[][4]) {
if ((i < 0 || i >= 4) || (j < 0 || j >= 4) || M[i][j] == 0)
return false;
return true;
}
bool find(int M[][4]) {
int source, dest;
int W = 4*4+2;
use_graph g(W);
int k = 1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (M[i][j] != 0) {
if (is_okay(i, j+1, M))
g.add_side(k, k+1);
if (is_okay(i, j-1, M))
g.add_side(k, k-1);
if (j < 4-1 && is_okay(i+1, j, M))
g.add_side(k, k+4);
if (i > 0 && is_okay(i-1, j, M))
g.add_side(k, k-4);
}
if (M[i][j] == 1)
source = k;
if (M[i][j] == 2)
dest = k;
k++;
}
}
return g.search(source, dest);
}
int main() {
int M[4][4] = { {0, 3, 0, 1}, {3, 0, 3, 3}, {2, 3, 0, 3}, {0, 0, 3, 0} };
(find(M) == true) ?
cout << "Possible" : cout << "Not Possible" << endl;
return 0;
}
आउटपुट
Not Possible
