컨셉
주어진 숫자 그리드에 대해 최대 길이의 뱀 시퀀스를 결정하고 표시합니다. 최대 길이의 뱀 시퀀스가 여러 개 존재하는 경우 그 중 하나를 표시하는 것으로 관찰되었습니다.
실제로, 스네이크 시퀀스는 그리드의 인접한 숫자로 구성되어 각 숫자에 대해 오른쪽 또는 그 아래의 숫자가 +1 또는 -1 값이 되도록 합니다. 여기에서 예를 들어 그리드에서 위치 (a, b)를 지정하면 해당 숫자가 ± 1이면 오른쪽으로 이동할 수 있습니다(예:(a, b+1) ± 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
예
// 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)