หาเส้นทางต่อเนื่องที่ยาวที่สุดจากตัวอักษรเริ่มต้นในเมทริกซ์ (C++)

ให้เมทริกซ์ของตัวอักษรต่างๆ เริ่มจากตัวอักษรหนึ่ง ต้องหาเส้นทางที่ยาวที่สุดโดยเคลื่อนที่ไปยังตัวอักษรที่มีค่ามากกว่าตัวอักษรปัจจุบัน 1 หน่วย (Consecutive) และต้องอยู่ติดกัน 8 ทิศทาง

เริ่มจาก E

ใช้ Depth First Search (DFS) ร่วมกับ Dynamic Programming (Memoization) เพื่อหลีกเลี่ยงการคำนวณซ้ำของ Sub-problems

ตัวอย่างโค้ด

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

// ทิศทาง 8 ทิศ: ขวา, ล่างขวา, ล่าง, ล่างซ้าย, ซ้าย, บนซ้าย, บน, บนขวา
int dx[] = {0, 1, 1, -1, 1, 0, -1, -1};
int dy[] = {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) {
    return (i >= 0 && j >= 0 && i < ROW && j < COL);
}

bool isAdjacent(char prev, char curr) {
    return ((curr - prev) == 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 + dx[k], j + dy[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; // รีเซ็ตค่า memo

    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 + dx[k], j + dy[k], start));
            }
        }
    }
    return len;
}

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

ผลลัพธ์

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

ความซับซ้อนของเวลา

O(ROW × COL) เนื่องจากแต่ละเซลล์ถูกคำนวณสูงสุด 1 ครั้งเท่านั้น (Memoization)