এই সমস্যায়, আমাদের একটি 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
