इस समस्या में, हमें एक मैटिक्स दिया जाता है जिसमें aplhabets (केवल लोअरकेस) होता है और हमें मैट्रिक्स के ऊपर बाएं से नीचे दाईं ओर दिए गए मैट्रिक्स में सभी पैलिड्रोमिक पथ प्रिंट करने होते हैं।
इस समस्या में अनुमत चालें दाएँ और नीचे हैं। विकर्ण चाल की अनुमति नहीं है।
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -
Input: matrix[][] ={
{"xxxy",
"yxxx",
"xyyx"}
Output: xxxxxx , xxxxxx , xyxxyx व्याख्या
आइए wrt से 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
स्पष्टीकरण में ही हमने समस्या के समाधान की नींव रखी है। हम ऊपर-बाएं से नीचे-दाएं तक सभी पथ ढूंढेंगे और उन सभी को प्रिंट करेंगे जो पैलिंड्रोमिक पथ को परिणाम देते हैं।
उदाहरण
नीचे दिया गया उदाहरण समाधान को स्पष्ट करेगा -
#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