इस समस्या में, हमें एक 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
