Tìm đường đi từ ô góc đến ô giữa trong mê cung C++

Cho mê cung NxN (N lẻ), mỗi ô chứa số n. Từ ô (i,j) có thể nhảy đúng n bước theo 4 hướng (lên, xuống, trái, phải). Tìm tất cả đường đi từ 4 góc đến ô giữa.

Ví dụ (N=9)

Mê cung 9x9 với các số cho trước. Kết quả 5 đường đi.

Thuật toán: DFS + Backtracking

• Từ 4 góc, DFS thử 4 hướng.
• Bước nhảy = giá trị ô hiện tại.
• Kiểm tra hợp lệ: trong bounds, chưa thăm.
• Đến ô giữa (N/2, N/2) → in đường đi.

Triển khai C++

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

#define N 9
int maze[N][N] = {
    {3,4,4,4,7,3,4,6,3},
    {6,7,5,6,6,2,6,6,2},
    {3,3,4,3,2,5,4,7,2},
    {6,5,5,1,2,3,6,5,6},
    {3,3,4,3,0,1,4,3,4},
    {3,5,4,3,2,1,3,3,5},
    {3,5,4,3,2,6,4,4,3},
    {3,5,1,3,7,5,3,6,3},
    {6,2,4,3,4,5,4,5,1}
};

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool isValid(set<pair<int,int>>& vis, pair<int,int> p) {
    return p.first >= 0 && p.first < N && p.second >= 0 && p.second < N && !vis.count(p);
}

void printPath(list<pair<int,int>>& path) {
    for (auto& p : path) cout << "(" << p.first << "," << p.second << ")->";
    cout << "MIDDLE\n\n";
}

void dfs(pair<int,int> curr, list<pair<int,int>>& path, set<pair<int,int>>& vis) {
    if (curr.first == N/2 && curr.second == N/2) { printPath(path); return; }
    
    int jump = maze[curr.first][curr.second];
    for (int i = 0; i < 4; i++) {
        int nr = curr.first + dr[i] * jump;
        int nc = curr.second + dc[i] * jump;
        pair<int,int> nxt = {nr, nc};
        if (isValid(vis, nxt)) {
            vis.insert(nxt);
            path.push_back(nxt);
            dfs(nxt, path, vis);
            path.pop_back();
            vis.erase(nxt);
        }
    }
}

int main() {
    int corners[4][2] = {{0,0}, {0,N-1}, {N-1,0}, {N-1,N-1}};
    for (auto& c : corners) {
        pair<int,int> start = {c[0], c[1]};
        list<pair<int,int>> path = {start};
        set<pair<int,int>> vis = {start};
        dfs(start, path, vis);
    }
    return 0;
}

Kết quả (5 đường đi)

(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

Độ phức tạp: Số đường đi có thể lớn (exponential), phù hợp N nhỏ.