数据结构
网络
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 次查看
