对于给定的数字网格,确定最大长度的Snake序列并显示它。已经观察到,如果存在多个最大长度的蛇形序列,则显示其中任何一个。
实际上,蛇形序列由网格中的相邻数字组成,因此对于每个数字,右侧的数字或其下方的数字为其值的+1或-1。例如,在这里,例如,如果我们位于网格中的位置(a,b),则如果该数字为±1,则可以向右移动(即(a,b + 1)),或者如果向右移动则可以向下移动(即(a + 1,b))该数字为±1。
例如,
10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8
在上面的网格中,最大蛇形序列为:(10,9,8,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
// C++ program to find maximum length //蛇序列并打印 #include <bits/stdc++.h> using namespace std; #define M 4 #define N 4 struct Point{ int X, Y; }; //显示查找最大长度的Snake序列路径的功能 //(a,b)对应于蛇的尾巴 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; } //显示函数以查找最大长度的Snake序列 void findSnakeSequence(int mat1[M][N]){ //显示表以存储子问题的结果 int lookup1[M][N]; //用于初始化0- memset(lookup1, 0, sizeof lookup1); //用于存储Snake序列的最大长度 int max_len1 = 0; //用于将坐标存储到蛇的尾巴 int max_row1 = 0; int max_col1 = 0; //用于自下而上地填写表格 for (int a = 0; a < M; a++){ for (int b = 0; b < N; b++){ //执行除(0,0)单元格 if (a || b){ //看上面 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; } } //向左看 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 蛇的顺序是: " << max_len1 << endl; //确定最大长度的Snake序列路径 list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1); cout << "蛇的顺序是:"; for (auto it = path1.begin(); it != path1.end(); it++) cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;} //驱动程式码 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 蛇的顺序是: 6 蛇的顺序是: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)