এই সমস্যায়, আমাদের একটি mXn ২D ম্যাট্রিক্স দেওয়া আছে এবং আমাদের টপ-লেফট থেকে বটম-রাইট পর্যন্ত সব সম্ভাব্য পাথ প্রিন্ট করতে হবে। ট্রভার্সালের জন্য, আমরা ম্যাট্রিক্সে শুধু ডানে এবং নিচে যেতে পারি।
একটি উদাহরণ নিয়ে টপিকটি ভালোভাবে বুঝতে চাই −
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
