এই সমস্যায়, একটি mXn 2D ম্যাট্রিক্স দেওয়া থাকে এবং আমাদের ম্যাট্রিক্সের টপ লেফ্ট থেকে বটম রাইট পর্যন্ত সব সম্ভাব্য পথ প্রিন্ট করতে হবে। ট্রাভার্সালের জন্য আমরা চারদিকেই যেতে পারি অর্থাৎ লেফ্ট, রাইট, টপ, বটম।
যদিও রাইট এবং টপ মুভ খুব কম ব্যবহৃত হয় কিন্তু কখনও কখনও এগুলো উপকারী হয়।
উদাহরণ দিয়ে বুঝি:
ইনপুট:
1 3 5 2 8 9
আউটপুট:
1 -> 3 -> 5 -> 9 1 -> 3 -> 8 -> 9 1 -> 2 -> 8 -> 9
এই সমস্যাটি সমাধান করতে, আমরা একটা সেল থেকে অন্য সেলে যাব এবং ডাউন এবং রাইট যাওয়ার পথ প্রিন্ট করব। আমরা ম্যাট্রিক্সের প্রতিটি সেলের জন্য এটি রিকার্শিভলি করব।
C++ উদাহরণ
#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
