Đường đi liên tiếp dài nhất từ ký tự bắt đầu cho trước

Cho ma trận các ký tự khác nhau. Từ một ký tự bắt đầu, tìm đường đi dài nhất bằng cách di chuyển đến các ô lân cận (8 hướng) chứa ký tự liên tiếp theo trong bảng chữ cái (ví dụ: 'a' → 'b' → 'c'...).

Sử dụng DFS kết hợp quy hoạch động (memorization) để tránh tính toán lặp lại các bài toán con.

Đầu vào và Đầu ra

Đầu vào: Ma trận 3x3:
a c d
h b a
i g f
Ký tự bắt đầu: 'e'

Đầu ra: Maximum consecutive path: 5
(Đường đi: e → f → g → h → i)

Thuật toán

Hàm findLongestLen(i, j, prev): Trả về độ dài đường đi dài nhất từ ô (i,j) với ký tự trước là prev.

• Nếu ô không hợp lệ hoặc ký tự hiện tại không liên tiếp sau prev → trả về 0.
• Nếu đã tính toán longestPath[i][j] → trả về giá trị đã lưu.
• Đệ quy thử 8 hướng lân cận, lấy max của 1 + findLongestLen(...).
• Lưu và trả về kết quả.

Hàm getLen(start): Duyệt toàn bộ ma trận tìm ô chứa start, từ đó gọi findLongestLen cho 8 hướng lân cận, lấy max.

Ví dụ C++

#include <iostream>
#define ROW 3
#define COL 3
using namespace std;

int x[] = {0, 1, 1, -1, 1, 0, -1, -1};
int y[] = {1, 0, 1, 1, -1, -1, 0, -1};
int longestPath[ROW][COL];
char mat[ROW][COL] = {
    {'a','c','d'},
    {'h','b','a'},
    {'i','g','f'}
};

bool isvalid(int i, int j) {
    return (i >= 0 && i < ROW && j >= 0 && j < COL);
}
bool isadjacent(char previous, char current) {
    return (current - previous == 1);
}

int findLongestLen(int i, int j, char prev) {
    if (!isvalid(i, j) || !isadjacent(prev, mat[i][j])) return 0;
    if (longestPath[i][j] != -1) return longestPath[i][j];
    int len = 0;
    for (int k=0; k<8; k++)
        len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));
    return longestPath[i][j] = len;
}

int getLen(char start) {
    for(int i=0;i<ROW;i++) for(int j=0;j<COL;j++) longestPath[i][j] = -1;
    int len = 0;
    for (int i=0; i<ROW; i++) {
        for (int j=0; j<COL; j++) {
            if (mat[i][j] == start) {
                for (int k=0; k<8; k++)
                    len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start));
            }
        }
    }
    return len;
}

int main() {
    char start;
    cout << "Enter Starting Point (a-i): "; cin >> start;
    cout << "Maximum consecutive path: " << getLen(start);
    return 0;
}

Kết quả

Enter Starting Point (a-i): e
Maximum consecutive path: 5