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