इस समस्या में, हमें एक mXn 2D मैट्रिक्स दिया जाता है और हमें मैट्रिक्स के ऊपर बाएँ से नीचे दाईं ओर सभी संभावित रास्तों को प्रिंट करना होता है। ट्रैवर्सल के लिए, हम चारों दिशाओं यानी बाएँ, दाएँ, ऊपर, नीचे में घूम सकते हैं।
सोचा कि दाएं और ऊपर की चाल शायद ही कभी उपयोग की जाती हैं लेकिन ये कभी-कभी फायदेमंद हो सकती हैं।
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं:
इनपुट:
1 3 5 2 8 9
आउटपुट:
1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9
इस समस्या को हल करने के लिए हम एक सेल से दूसरे सेल में जाएंगे और नीचे और दाएं जाने पर पाथ प्रिंट करेंगे। हम मैट्रिक्स में प्रत्येक सेल के लिए इसे पुनरावर्ती रूप से करेंगे।
आइए एक प्रोग्राम देखें जो पुनरावर्ती एल्गोरिथम को लागू करता है -
उदाहरण
#include<iostream>
using namespace std;
void printPathTPtoBR(int *mat, int i, int j, int m, int n, int *path, int pi) {
if (i == m - 1) {
for (int k = j; k < n; k++)
path[pi + k - j] = *((mat + i*n) + k);
for (int l = 0; l < pi + n - j; l++)
cout << path[l] << " ";
cout << endl;
return;
}
if (j == n - 1) {
for (int k = i; k < m; k++)
path[pi + k - i] = *((mat + k*n) + j);
for (int l = 0; l < pi + m - i; l++)
cout << path[l] << " ";
cout << endl;
return;
}
path[pi] = *((mat + i*n) + j);
printPathTPtoBR(mat, i+1, j, m, n, path, pi + 1);
printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1);
}
void findPath(int *mat, int m, int n) {
int *path = new int[m+n];
printPathTPtoBR(mat, 0, 0, m, n, path, 0);
}
int main() {
int mat[2][3] = {
{1, 2, 3},
{4, 5, 6}
};
cout<<"Path from top-left to bottom-rigth of matrix are :\n";
findPath(*mat, 2, 3);
return 0;
} आउटपुट
Path from top-left to bottom-rigth of matrix are : 1 4 5 6 1 2 5 6 1 2 3 6