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

#define SIZE 12

void printMaze(char maze[][SIZE])
{
    for (int row = 0; row < SIZE; ++row)
    {
        for (int column = 0; column < SIZE; ++column)
        {
            printf("%c ", maze[row][column]);
        }

        puts("");
    }

    puts("");
}

void mazeGenerator(char maze[][SIZE])
{
    for (int row = 0; row < SIZE; ++row)
    {
        for (int column = 0; column < SIZE; ++column)
        {
            if (row == 0 || row == SIZE - 1 ||
                column == 0 || column == SIZE - 1)
            {
                maze[row][column] = '#';
            }
            else
            {
                maze[row][column] = '.';
            }
        }
    }

    for (int row = 1; row < SIZE - 1; ++row)
    {
        for (int column = 1; column < SIZE - 1; ++column)
        {
            if (rand() % 4 == 0)
            {
                maze[row][column] = '#';
            }
        }
    }

    maze[1][1] = '.';
    maze[SIZE - 2][SIZE - 2] = '.';

    maze[SIZE - 2][SIZE - 1] = '.';
}

int mazeTraverse(char maze[][SIZE],
                 int row,
                 int column)
{
    if (row < 0 || row >= SIZE ||
        column < 0 || column >= SIZE)
    {
        return 1;
    }

    if (maze[row][column] != '.')
    {
        return 0;
    }

    maze[row][column] = 'X';

    if (mazeTraverse(maze, row, column + 1))
    {
        return 1;
    }

    if (mazeTraverse(maze, row + 1, column))
    {
        return 1;
    }

    if (mazeTraverse(maze, row, column - 1))
    {
        return 1;
    }

    if (mazeTraverse(maze, row - 1, column))
    {
        return 1;
    }

    maze[row][column] = '.';

    return 0;
}

int main(void)
{
    char maze[SIZE][SIZE];

    srand((unsigned int)time(NULL));

    mazeGenerator(maze);

    printf("Generated maze:\n\n");
    printMaze(maze);

    if (mazeTraverse(maze, 1, 1))
    {
        printf("The maze was solved.\n");
    }
    else
    {
        printf("No path was found.\n");
    }

    printf("\nMaze after traversal:\n\n");
    printMaze(maze);

    return 0;
}