数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用 C++ 打印矩阵中从左上角到右下角的所有回文路径
在这个问题中，我们得到一个包含字母（仅小写字母）的矩阵，我们必须打印出从矩阵的左上角到右下角的所有回文路径。
此问题中允许的移动是向右和向下。不允许对角线移动。
让我们来看一个例子来理解这个问题：
Input: matrix[][] ={
{"xxxy",
"yxxx",
"xyyx"}
Output: 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
更新于：2020-7-14
147 次浏览
广告