এই সমস্যায়, আমাদেরকে একটি ম্যাটিক্স দেওয়া হয়েছে যেটিতে aplhabets রয়েছে (শুধুমাত্র ছোট হাতের) এবং আমাদের ম্যাট্রিক্সের উপরের বাম থেকে নীচের ডানদিকে প্রদত্ত ম্যাট্রিক্সের সমস্ত প্যালিড্রোমিক পাথ প্রিন্ট করতে হবে৷
এই সমস্যায় অনুমোদিত পদক্ষেপগুলি ডান এবং নীচে। তির্যক চলন অনুমোদিত নয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক −
Input: matrix[][] ={
{"xxxy",
"yxxx",
"xyyx"}
Output: xxxxxx , xxxxxx , xyxxyx ব্যাখ্যা
i th পজিশন wrt ব্যবহার করে উপরের বাম থেকে নীচে ডানদিকে সমস্ত বৈধ পদক্ষেপগুলি দেখতে দিন অবস্থান।
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
ব্যাখ্যাতেই, আমরা সমস্যার সমাধানের ভিত্তি স্থাপন করেছি৷ আমরা উপরের-বাম থেকে নীচে-ডান পর্যন্ত সমস্ত পথ খুঁজে পাব এবং প্যালিন্ড্রোমিক পথের ফলাফল দেয় এমন সমস্তগুলিকে প্রিন্ট করব৷
উদাহরণ
নিচের উদাহরণটি সমাধানটি ব্যাখ্যা করবে −
#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
