Khái niệm
Đối với một lưới các số nhất định, hãy xác định độ dài tối đa của dãy Rắn và hiển thị nó. Người ta đã quan sát thấy rằng nếu tồn tại nhiều dãy rắn với độ dài tối đa, hãy hiển thị bất kỳ ai trong số đó.
Trên thực tế, một chuỗi con rắn được tạo thành từ các số liền kề trong lưới sao cho mỗi số, thì số ở bên phải hoặc số bên dưới nó là +1 hoặc -1 giá trị của nó. Ví dụ:ở đây, nếu chúng ta đặt vị trí (a, b) trong lưới, chúng ta có thể di chuyển sang phải, tức là (a, b + 1) nếu số đó là ± 1 hoặc di chuyển xuống tức là (a + 1, b) nếu số đó là ± 1.
Ví dụ:
10, 7, 6, 3 9, 8, 7, 6 8, 4, 2, 7 2, 2, 2, 8
Trong lưới trên, chuỗi con rắn tối đa là:(10, 9, 8, 7, 6, 7, 8)
Hình dưới đây cho thấy tất cả các con đường có thể có -
10 7 →6 3 ↓ ↓ ↓ 9 → 8 → 7→ 6 ↓↓ 8 4 2 7 ↓ 2 2 2 8
Phương pháp
Ở đây, khái niệm là thực hiện Lập trình động. Đối với mỗi ô của ma trận, chúng tôi giữ độ dài dài nhất của một con rắn kết thúc trong ô hiện tại. Bây giờ dãy con rắn có độ dài dài nhất sẽ có giá trị lớn nhất. Ở đây, ô có giá trị dài nhất sẽ tương ứng với đuôi của con rắn. Để in hình con rắn, chúng tôi yêu cầu phải quay ngược từ đuôi trở lại đầu rắn. Giả sử T [a] [b] đại diện cho chiều dài lớn nhất của một con rắn kết thúc tại ô (a, b), sau đó đối với ma trận M đã cho, quan hệ Lập trình động được định nghĩa là -
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
Ví dụ
// 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;
} Đầu ra
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)