ম্যাট্রিক্সে টপ লেফ্ট থেকে বটম রাইট পর্যন্ত সব প্যালিনড্রোমিক পথ প্রিন্ট করা C++-তে

এই সমস্যায়, একটি ম্যাট্রিক্স দেওয়া থাকে যেটিতে অ্যালফাবেট (লোয়ারকেস ওনলি) থাকে এবং আমাদের ম্যাট্রিক্সের টপ লেফ্ট থেকে বটম রাইট পর্যন্ত সব প্যালিনড্রোমিক পথ প্রিন্ট করতে হবে।

এই সমস্যায় অ্যালোয়েড মুভ হলো রাইট এবং ডাউন। ডায়াগোনাল মুভ অ্যালোয়েড নয়।

উদাহরণ দিয়ে বুঝি:

ইনপুট: matrix[][] = { {"xxxy", "yxxx", "xyyx"} আউটপুট: xxxxxx, xxxxxx, xyxxyx

ব্যাখ্যা

টপ লেফ্ট থেকে বটম রাইট পর্যন্ত i^th পজিশন সাপেক্ষে সব ভ্যালিড মুভ দেখা যাক।

i00 -> i01 -> i02 -> i03 -> i13 -> i23 = xxxyxx i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx ... i00 -> i10 -> i20 -> i21 -> i22 -> i23 = xyxyyx

সব সম্ভাব্য আউটকামের মধ্যে, আমাদের শুধু প্যালিনড্রোমিক পথ যেগুলো আউটকাম হিসেবে দেয় সেগুলো দরকার:

i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx i00 -> i01 -> i02 -> i12 -> i13 -> i23 = xxxxxx i00 -> i10 -> i11 -> i12 -> i22 -> i23 = xyxxyx
ব্যাখ্যাতেই আমরা সমস্যাটির সমাধানের ভিত্তি রেখে দিয়েছি। আমরা টপ-লেফ্ট থেকে বটম-রাইট পর্যন্ত সব পথ খুঁজে বের করব এবং যেসব প্যালিনড্রোমিক পথ আউটকাম দেয় সেগুলো প্রিন্ট করব।
C++ উদাহরণ
#include<iostream> using namespace std; #define N 4 int printPalindrome(string str){ int len = str.length() / 2; for (int i = 0; i < len; i++) { if (str[i] != str[str.length() - i - 1]) return 0; } cout<<str<<endl; } void findPath(string str, char a[][N], int i, int j, int m, int n) { if (j < m - 1 || i < n - 1) { if (i < n - 1) findPath(str + a[i][j], a, i + 1, j, m, n); if (j < m - 1) findPath(str + a[i][j], a, i, j + 1, m, n); } else { str = str + a[n - 1][m - 1]; printPalindrome(str); } } int main() { char matrix[][N] = { { 'x', 'y', 'x', 'y' }, { 'y', 'x', 'x', 'y' }, { 'y', 'x', 'y', 'x' } }; string str = ""; cout<<"Palimdromic path are : "; findPath(str, matrix, 0, 0, 4, 3); return 0; }
আউটপুট
Palimdromic path are: xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx xyxxyx