Tìm chuỗi Snake dài nhất trong C++

Khái niệm

Cho một lưới số, xác định chuỗi Snake dài nhất và hiển thị nó. Nếu tồn tại nhiều chuỗi Snake cùng độ dài lớn nhất, hiển thị bất kỳ chuỗi nào.

Một chuỗi Snake được cấu thành từ các số liền kề trong lưới sao cho đối với mỗi số, số bên phải hoặc số bên dưới nó lớn hơn hoặc nhỏ hơn 1 đơn vị. Ví dụ, nếu đang ở vị trí (a, b) trong lưới, ta có thể sang phải (a, b+1) nếu số đó chênh lệch ±1 hoặc xuống dưới (a+1, b) nếu số đó chênh lệch ±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 Snake dài nhất là: (10, 9, 8, 7, 6, 7, 8)

Hình dưới minh họa các đường đi:

10  7 → 6  3
↓   ↓   ↓
9 → 8 → 7→ 6
↓   ↓
8   4   2   7
↓
2   2   2   8

Phương pháp

Ý tưởng là sử dụng Quy hoạch động. Với mỗi ô của ma trận, lưu độ dài lớn nhất của chuỗi Snake kết thúc tại ô đó. Chuỗi Snake dài nhất sẽ có giá trị lớn nhất. Ô có giá trị lớn nhất tương ứng với đuôi của con rắn. Để in chuỗi, cần truy ngược từ đuôi về đầu. Giả sử T[a][b] biểu diễn độ dài lớn nhất của chuỗi Snake kết thúc tại ô (a, b), thì với ma trận M, mối quan hệ quy hoạch động được định nghĩa như sau:

T[0][0] = 0
T[a][b] = max(T[a][b], T[a][b – 1] + 1) nếu M[a][b] = M[a][b – 1] ± 1
T[a][b] = max(T[a][b], T[a – 1][b] + 1) nếu M[a][b] = M[a – 1][b] ± 1

Ví dụ

// Chương trình C++ tìm chuỗi Snake dài nhất và in ra
#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 4
struct Point{
    int X, Y;
};

// Hàm tìm đường đi chuỗi Snake dài nhất (a, b) là đuôi con rắn
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;
}

// Hàm tìm chuỗi Snake dài nhất
void findSnakeSequence(int mat1[M][N]){
    // Bảng lưu kết quả bài toán con
    int lookup1[M][N];
    // Khởi tạo bằng 0
    memset(lookup1, 0, sizeof lookup1);
    // Lưu độ dài lớn nhất của chuỗi Snake
    int max_len1 = 0;
    // Lưu tọa độ đuôi con rắn
    int max_row1 = 0;
    int max_col1 = 0;
    // Điền bảng theo cách bottom-up
    for (int a = 0; a < M; a++){
        for (int b = 0; b < N; b++){
            // Thực hiện trừ ô (0, 0)
            if (a || b){
                // Xem ô trên
                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;
                    }
                }
                // Xem ô trái
                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 << "Độ dài lớn nhất của chuỗi Snake là: " << max_len1 << endl;
    // Tìm đường đi chuỗi Snake dài nhất
    list<Point> path1 = findPath(lookup1, mat1, max_row1, max_col1);
    cout << "Chuỗi Snake là:";
    for (auto it = path1.begin(); it != path1.end(); it++)
        cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")";
}

// Chương trình chính
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

Độ dài lớn nhất của chuỗi Snake là: 6
Chuỗi Snake là:
10 (0, 0)
9 (1, 0)
8 (1, 1)
7 (1, 2)
6 (1, 3)
7 (2, 3)
8 (3, 3)