#include <stdio.h>

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

        puts("");
    }

    puts("");
}

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

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

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

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

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

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

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

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

    return 0;
}

int main(void)
{
    int rows;
    int columns;

    printf("Enter number of rows: ");
    scanf("%d", &rows);

    printf("Enter number of columns: ");
    scanf("%d", &columns);

    char maze[100][100];

    printf("Enter the maze:\n");

    for (int row = 0; row < rows; ++row)
    {
        for (int column = 0; column < columns; ++column)
        {
            scanf(" %c", &maze[row][column]);
        }
    }

    printf("\nMaze before traversal:\n\n");
    printMaze(maze, rows, columns);

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

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

    return 0;
}