資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學矩陣中迴文路徑的數量
迴文路徑在解決涉及模式和序列的各種問題中非常有用。它可以用於在不反轉的情況下找到迷宮中的正確路徑、字母序列中的迴文等等，它還可以用於識別對稱模式和結構。在本文中，我們將討論迴文路徑以及如何使用 C++ 在矩陣中找到此類路徑。
迴文是一系列字母、數字或字元，它們具有相同的起點和終點。此外，從左到右和從右到左讀取時它們相同。矩陣中的路徑是一系列單元格，從第一個單元格 (1, 1) 開始到最右邊的最後一個單元格。迴文序列在對稱矩陣中更為常見。我們將得到一組矩陣，我們必須在其中找到最大數量的迴文路徑。
輸入輸出場景
我們得到矩陣。該矩陣中迴文路徑的數量是輸出。
Input: matrix[3][4] = {{1, 1, 1, 2}, {2, 1, 1, 1}, {1, 2, 2, 1}}
Output: 3
Input: matrix[3][4] = {{1, 1, 1, 2}, {2, 1, 1, 1}, {1, 2, 2, 1}}
Output: 2
這裡，在矩陣[3][4] = {{1, 1, 1, 2}, {2, 1, 1, 1}, {1, 2, 2, 1}} 的情況下，我們有 3 條迴文路徑。它們如下所示：
111111- (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3)
111111- (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (2, 3)
121121- (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3)
使用遞迴
我們將使用遞迴函式來查詢矩陣中的迴文路徑。
首先，我們將建立一個函式來檢查字串（或路徑）是否為迴文。
要檢查這一點，我們將從字串的第一位到最後一位執行一個**while**迴圈。我們檢查第一個和最後一個字元、第二個和倒數第二個字元等等之間的相似性。
然後，我們建立一個函式來查詢總共迴文的路徑。首先，我們分別使用**mat.size()**和**mat[0].size()**找到總行數和總列數。然後，我們檢查路徑是否為迴文。如果函式不在最後一個單元格，則函式遞迴呼叫自身。
為了向前移動，透過將列加 1 並保持行不變來遞迴呼叫函式。為了向下移動，透過保持列不變並將行加 1 來遞迴呼叫函式。
向前和向下遞迴呼叫的結果之和給出了給定矩陣中迴文路徑的總數。
示例
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool palindrome(const string & string) {
int start = 0, end = string.length() - 1;
while (start < end) {
if (string[start] != string[end]) {
return false;
}
start++;
end--;
}
return true;
}
int palindromicPaths(vector < vector < int >> & mat, int i, int j, string path){
int rows = mat.size();
int columns = mat[0].size();
if (i < 0 || i >= rows || j < 0 || j >= columns) {
return 0;
}
// Appending the value of current matrix cell
path += to_string(mat[i][j]);
if (i == rows - 1 && j == columns - 1) {
if (palindrome(path)) {
return 1;
}
return 0;
}
int forward = palindromicPaths(mat, i, j + 1, path);
int below = palindromicPaths(mat, i + 1, j, path);
int totalCount = forward + below;
return totalCount;
}
int main() {
vector<vector<int>> mat = {{1, 1, 1, 2}, {2, 1, 1, 1}, {1, 2, 2, 1}};
cout << "Number of palindromic paths in the matrix: " <<
palindromicPaths(mat, 0, 0, "") << endl;
return 0;
}
輸出
Number of palindromic paths in the matrix: 3
結論
我們討論瞭如何在矩陣中查找回文路徑。我們使用了遞迴函式來查詢可能的路徑。我們可以使用動態規劃來提高程式碼效率。為此，我們可以在向量中儲存字串（或路徑）。使用**記憶化**對映可以降低空間複雜度。
234 次檢視
