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

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

ตัวอย่าง Input และ Output

Matrix:
a c d
h b a
i g f

Input: เริ่มจาก 'e'
Output: Maximum consecutive path: 5
(เส้นทาง: e → f → g → h → i)

อัลกอริทึม: DFS + Dynamic Programming (Memoization)

ฟังก์ชัน findLongestLen(i, j, prev)

Input: ตำแหน่ง (i, j) และตัวอักษรก่อนหน้า

Output: ความยาวเส้นทางสูงสุดจากตำแหน่งนี้

ขั้นตอน:

1. Base Case - Invalid: ถ้าพิกัดอยู่นอกเมทริกซ์ หรือตัวอักษรปัจจุบันไม่ได้มากกว่า prev ทีละ 1 → คืน 0
2. Memoization: ถ้า longestPath[i][j] != -1 → คืนค่าทันที
3. DFS 8 ทิศทาง: ลองเดินไปทุกทิศทาง คำนวณ 1 + findLongestLen(...) และหาค่า max
4. เก็บผลลัพธ์ใน longestPath[i][j] และคืนค่า

ฟังก์ชัน getLen(start)

วนหาตำแหน่งที่มีตัวอักษรเท่ากับ start แล้วเรียก findLongestLen จากเพื่อนบ้าน 8 ทิศทาง

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

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

int x[] = {0, 1, 1, -1, 1, 0, -1, -1}; // 8 ทิศทางแถว
int y[] = {1, 0, 1, 1, -1, -1, 0, -1}; // 8 ทิศทางคอลัมน์

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 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 + 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;
}

Output

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

ความซับซ้อน

• Time: O(ROW × COL) - แต่ละเซลล์คำนวณสูงสุด 1 ครั้ง
• Space: O(ROW × COL) - ตาราง memoization