ในปัญหานี้ เราได้รับ matix ที่มี aplhabets (ตัวพิมพ์เล็กเท่านั้น) และเราต้องพิมพ์พา ธ palidromic ทั้งหมดในเมทริกซ์ที่กำหนดจากบนซ้ายไปล่างขวาของเมทริกซ์
การย้ายที่อนุญาตในปัญหานี้ถูกต้องและลดลง ไม่อนุญาตให้เคลื่อนที่ในแนวทแยง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
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
