数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 C++ 中查找最大长度的蛇形序列
概念
针对给定的数字网格，确定最大长度的蛇形序列并显示它。如果存在多个具有最大长度的蛇形序列，则显示其中任何一个。
实际上，蛇形序列是由网格中相邻的数字组成，使得对于每个数字，其右侧或下方的数字的值与其自身的值相差 +1 或 -1。例如，如果我们在网格中的位置 (a, b)，我们可以向右移动到 (a, b+1)，如果该数字是 ± 1，或者向下移动到 (a+1, b)，如果该数字是 ± 1。
例如：
10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8
在上面的网格中，最大蛇形序列为：(10, 9, 8, 7, 6, 7, 8)
下图显示了所有可能的路径：
10 7 →6 3 ↓ ↓ ↓ 9 → 8 → 7→ 6 ↓↓ 8 4 2 7 ↓ 2 2 2 8
方法
这里，核心思想是实现动态规划。对于矩阵的每个单元格，我们都保留以当前单元格结尾的蛇的最大长度。现在，最长的蛇形序列将具有最大值。这里，最大值的单元格将对应于蛇的尾部。为了打印蛇，我们需要从尾部回溯到蛇的头。假设 T[a][b] 表示以单元格 (a, b) 结尾的蛇的最大长度，那么对于给定的矩阵 M，动态规划关系定义为：
T[0][0] = 0 T[a][b] = max(T[a][b], T[a][b – 1] + 1) if M[a][b] = M[a][b – 1] ± 1 T[a][b] = max(T[a][b], T[a – 1][b] + 1) if M[a][b] = M[a – 1][b] ± 1
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
示例
// C++ program to find maximum length // Snake sequence and print it #include <bits/stdc++.h> using namespace std; #define M 4 #define N 4 struct Point{ int X, Y; }; // Shows function to find maximum length Snake sequence path // (a, b) corresponds to tail of the snake list<Point> findPath(int grid1[M][N], int mat1[M][N], int a, int b){ list<Point> path1; Point pt1 = {a, b}; path1.push_front(pt1); while (grid1[a][b] != 0){ if (a > 0 && grid1[a][b] - 1 == grid1[a - 1][b]){ pt1 = {a - 1, b}; path1.push_front(pt1); a--; } else if (b > 0 && grid1[a][b] - 1 == grid1[a][b - 1]){ pt1 = {a, b - 1}; path1.push_front(pt1); b--; } } return path1; } // Shows function to find maximum length Snake sequence void findSnakeSequence(int mat1[M][N]){ // Shows table to store results of subproblems int lookup1[M][N]; // Used to initialize by 0 memset(lookup1, 0, sizeof lookup1); // Used to store maximum length of Snake sequence int max_len1 = 0; // Used to store cordinates to snake's tail int max_row1 = 0; int max_col1 = 0; // Used to fill the table in bottom-up fashion for (int a = 0; a < M; a++){ for (int b = 0; b < N; b++){ // Perform except for (0, 0) cell if (a || b){ // look above if (a > 0 && abs(mat1[a - 1][b] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a - 1][b] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } // look left if (b > 0 && abs(mat1[a][b - 1] - mat1[a][b]) == 1){ lookup1[a][b] = max(lookup1[a][b], lookup1[a][b - 1] + 1); if (max_len1 < lookup1[a][b]){ max_len1 = lookup1[a][b]; max_row1 = a, max_col1 = b; } } } } } cout << "Maximum length of Snake sequence is: " << max_len1 << endl; // Determine maximum length Snake sequence path list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1); cout << "Snake sequence is:"; for (auto it = path1.begin(); it != path1.end(); it++) cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;} // Driver code int main(){ int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8},}; findSnakeSequence(mat1); return 0; }
输出
Maximum length of Snake sequence is: 6 Snake sequence is: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)
更新于: 2020-07-25
214 次浏览
广告