#include <stdio.h>

#define N 5 // Kích thước của mê cung

// Kiểm tra xem ô (x, y) có hợp lệ không
int isValid(int maze[N][N], int x, int y) {
    // Kiểm tra xem (x, y) có nằm trong mê cung và không phải là tường
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 0)
        return 1;
    return 0;
}

// Hàm đệ quy để tìm đường trong mê cung
int findPath(int maze[N][N], int x, int y, int sol[N][N]) {
    // Điểm đích được đạt được
    if (x == N - 1 && y == N - 1) {
        sol[x][y] = 1;
        return 1;
    }

    // Kiểm tra xem ô (x, y) có hợp lệ không
    if (isValid(maze, x, y) == 1) {
        // Đánh dấu ô hiện tại là một phần của đường đi
        sol[x][y] = 1;

        // Di chuyển sang phải
        if (findPath(maze, x + 1, y, sol) == 1)
            return 1;

        // Di chuyển xuống
        if (findPath(maze, x, y + 1, sol) == 1)
            return 1;

        // Nếu không thể di chuyển sang phải hoặc xuống, đánh dấu ô này là không hợp lệ
        sol[x][y] = 0;
        return 0;
    }

    return 0;
}

// In ra ma trận đường đi trong mê cung
void printSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}

// Hàm chính
int main() {
    int maze[N][N] = {
        {0, 1, 0, 1, 1},
        {0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0},
        {0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0}
    };

    // Khởi tạo ma trận lưu đường đi
    int sol[N][N] = {{0, 0, 0, 0, 0},
                     {0, 0, 0, 0, 0},
                     {0, 0, 0, 0, 0},
                     {0, 0, 0, 0, 0},
                     {0, 0, 0, 0, 0}};

    if (findPath(maze, 0, 0, sol) == 1)
        printSolution(sol);
    else
        printf("Không tìm thấy đường đi trong mê cung!");

    return 0;
}