इस समस्या में, हमें एक mXn 2D मैट्रिक्स दिया जाता है और हमें मैट्रिक्स के ऊपर बाईं ओर से नीचे दाईं ओर सभी संभावित रास्तों को प्रिंट करना होता है। ट्रैवर्सल के लिए, हम मैट्रिक्स में केवल दाएं और नीचे जा सकते हैं।
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input: 1 3 5 2 8 9 Output: 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;
} आउटपुट
मैट्रिक्स के ऊपर-बाएं से नीचे-दाएं तक का पथ है -
1 4 5 6 1 2 5 6 1 2 3 6