資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告