หา Path จาก Corner ไป Middle ใน Maze (Jump by Cell Value) ใน C++

โจทย์: Square maze N×N แต่ละ cell มีตัวเลข n จาก cell (i,j) เดินได้ n steps ใน 4 ทิศทาง: (i±n, j), (i, j±n) หา paths ทั้งหมดจาก corner ไป middle

ตัวอย่าง 9x9 maze → 5 paths

อัลกอริธึม: DFS + Backtracking

1. เริ่มจาก 4 corners
2. DFS:
• ถ้าถึง middle (N/2, N/2) → print path
• ลอง 4 ทิศทาง: คำนวณ next cell = curr + dir × value
• ถ้า valid (ใน bounds, ไม่เคยไป) → mark visited, recurse, backtrack

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

#include <bits/stdc++.h>
using namespace std;
#define N 9

bool is_ok(set<pair<int,int>> visited, pair<int,int> pt) {
    return pt.first >= 0 && pt.first < N && pt.second >= 0 && pt.second < N && visited.find(pt) == visited.end();
}

void display_path(list<pair<int,int>> path) {
    for (auto it = path.begin(); it != path.end(); it++)
        cout << "(" << it->first << ", " << it->second << ")->";
    cout << "MIDDLE" << endl;
}

int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = {0, 0, -1, 1};
int row[] = {0, 0, N-1, N-1};
int col[] = {0, N-1, 0, N-1};

void solve(int maze[N][N], list<pair<int,int>> &path, set<pair<int,int>> &visited, pair<int,int> &curr) {
    if (curr.first == N/2 && curr.second == N/2) {
        display_path(path); return;
    }
    for (int i = 0; i < 4; ++i) {
        int n = maze[curr.first][curr.second];
        int x = curr.first + dir_row[i] * n;
        int y = curr.second + dir_col[i] * n;
        pair<int,int> next = {x, y};
        if (is_ok(visited, next)) {
            visited.insert(next);
            path.push_back(next);
            solve(maze, path, visited, next);
            path.pop_back();
            visited.erase(next);
        }
    }
}

void search_path(int maze[N][N]) {
    list<pair<int,int>> path;
    set<pair<int,int>> visited;
    for (int i = 0; i < 4; ++i) {
        pair<int,int> pt = {row[i], col[i]};
        visited.insert(pt);
        path.push_back(pt);
        solve(maze, path, visited, pt);
        path.pop_back();
        visited.erase(pt);
    }
}

int main() {
    int maze[N][N] = { /* 9x9 matrix */ };
    search_path(maze);
}

เอาต์พุทตัวอย่าง

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE

Complexity

• Time: Exponential (worst case) แต่ maze จำกัดขนาดและ jump ควบคุม branching
• Space: O(N²) สำหรับ visited + path