Tìm độ dài đường đi liên tiếp dài nhất từ ký tự bắt đầu cho trước trong C++

Cho ma trận ký tự. 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 ô liền kề (8 hướng) có ký tự lớn hơn đúng 1 đơn vị (liền tiếp trong bảng chữ cái).

Sử dụng DFS kết hợp Dynamic Programming (memoization) để tránh tính lại sub-problem. Ma trận hướng: 8 hướng (x[], y[]).

Ví dụ

#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'}
};

int max(int a, int b) { return (a>b)?a:b; }

bool isvalid(int i, int j) {
    if (i < 0 || j < 0 || i >= ROW || j >= COL) return false;
    return true;
}

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