#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define N 5           //tabla merete
#define START_ROW 0   //kiindulo sor
#define START_COL 0   //kiindulo oszlop
#define DEST_ROW N-1  //cel sor
#define DEST_COL N-1  //cel oszlop


void initMaze(int maze[N][N]){
    int i, j;
    srand(time(0));
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
            maze[i][j] = rand()%2;
    maze[START_ROW][START_COL] = maze[DEST_ROW][DEST_COL] = 1; //kiindulas es cel legyen elerheto
}


void printMaze(int maze[N][N]){
    int i, j;
    printf("|");
    for(j=0; j<N*4-1; j++) printf("-");
    printf("|\n");
    for(i=0; i<N; i++){
        for(j=0; j<N; j++){
            printf("| %c ", maze[i][j]==1 ? '1' : ' ');
        }
        printf("|\n|");
        for(j=0; j<N*4-1; j++) printf("-");
        printf("|\n");
    }

}


int solveMaze(int maze[N][N], int solution[N][N], int row, int col){
    if(row == DEST_ROW && col == DEST_COL){ //elertuk a celt, keszen vagyunk
        solution[row][col] = 1;
        return 1;
    }
    if(row >= 0 && row < N && col >= 0 && col < N && maze[row][col] == 1 && solution[row][col] != 1){
        solution[row][col] = 1;
        if(solveMaze(maze, solution, row+1, col)) return 1; //megprobaljuk lefele
        if(solveMaze(maze, solution, row, col-1)) return 1; //megprobaljuk balra
        if(solveMaze(maze, solution, row, col+1)) return 1; //megprobaljuk jobbra
        solution[row][col] = 0; //egyik lepes sem vezetett megoldasra
    }
    return 0;
}


int main(){
    int maze[N][N], solution[N][N], i, j;
    initMaze(maze);
    printf("Labirintus:\n\n");
    printMaze(maze);
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
            solution[i][j] = 0;
    if(solveMaze(maze, solution, START_ROW, START_COL)){
        printf("\nEgy lehetseges megoldas:\n\n");
        printMaze(solution);
    }
    else{
        printf("\nNincs megoldas.\n\n");
    }
    return 0;
}


/*
int main(){
    int maze[N][N], solution[N][N], i, j, solvable=0;
    while(!solvable){
        initMaze(maze);
        for(i=0; i<N; i++)
            for(j=0; j<N; j++)
                solution[i][j] = 0;
        if(solveMaze(maze, solution, START_ROW, START_COL)) solvable = 1;
    }
    printf("Labirintus:\n\n");
    printMaze(maze);
    printf("\nEgy lehetseges megoldas:\n\n");
    printMaze(solution);
    return 0;
}
*/