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