#include <stdio.h>

#define SIZE 12

// Function prototypes
void mazeTraverse(char maze[SIZE][SIZE], int currentRow, int currentCol, int startRow, int startCol, int visited);
void printMaze(char maze[SIZE][SIZE]);

int main() {
    // Initialize the maze
    char maze[SIZE][SIZE] = {
        {'#','#','#','#','#','#','#','#','#','#','#','#'},
        {'#','.','.','.','#','.','.','.','.','.','.','#'},
        {'.','.','#','.','#','.','#','#','#','#','.','#'},
        {'#','#','#','.','#','.','.','.','.','#','.','#'},
        {'#','.','.','.','.','#','#','#','.','#','.','.'},
        {'#','#','#','#','.','#','.','#','.','#','.','#'},
        {'#','.','.','#','.','#','.','#','.','#','.','#'},
        {'#','#','.','#','.','#','.','#','.','#','.','#'},
        {'#','.','.','.','.','.','.','.','.','#','.','#'},
        {'#','#','#','#','#','#','.','#','#','#','.','#'},
        {'#','.','.','.','.','.','.','#','.','.','.','#'},
        {'#','#','#','#','#','#','#','#','#','#','#','#'}
    };
    
    // Starting position (from the maze - row 2, column 0)
    int startRow = 2, startCol = 0;
    
    printf("Initial Maze:\n");
    printMaze(maze);
    printf("\nStarting maze traversal...\n\n");
    
    // Start maze traversal
    mazeTraverse(maze, startRow, startCol, startRow, startCol, 0);
    
    return 0;
}

// Recursive function to traverse the maze using right-hand rule
void mazeTraverse(char maze[SIZE][SIZE], int currentRow, int currentCol, 
                  int startRow, int startCol, int visited) {
    
    // Mark current position with 'X' if it's not the start position
    if (!(currentRow == startRow && currentCol == startCol) || visited > 0) {
        maze[currentRow][currentCol] = 'X';
    }
    
    // Display the maze after each move
    printf("Step %d:\n", visited + 1);
    printMaze(maze);
    printf("\n");
    
    // Check if we've reached an exit (on the border but not at start)
    if ((currentRow == 0 || currentRow == SIZE-1 || currentCol == 0 || currentCol == SIZE-1) &&
        !(currentRow == startRow && currentCol == startCol)) {
        printf("Exit found at (%d, %d)!\n", currentRow, currentCol);
        return;
    }
    
    // Check if we've returned to start (no exit)
    if (visited > 0 && currentRow == startRow && currentCol == startCol) {
        printf("No exit found - returned to starting position.\n");
        return;
    }
    
    // Right-hand rule: always keep right hand on the wall
    // We'll check directions in this order: right, down, left, up
    // This simulates always trying to turn right first
    
    // Try moving in each direction according to right-hand rule
    int moved = 0;
    
    // Array of possible moves: right, down, left, up
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    // Find which direction we're currently facing (simplified approach)
    // For simplicity, we'll check all directions and prioritize right turns
    
    // Check right (relative to current direction - simplified)
    int newRow, newCol;
    
    // Try to move while following right-hand wall
    // The algorithm: always try to turn right, if not possible go straight, 
    // if not possible turn left, if not possible turn around
    
    // For this implementation, we'll use a simplified approach:
    // Check all four directions and move to the first valid one that follows right-hand rule
    
    for (int i = 0; i < 4 && !moved; i++) {
        // Check directions in a specific order to simulate right-hand rule
        int dirOrder[4] = {0, 1, 2, 3}; // right, down, left, up
        
        newRow = currentRow + directions[dirOrder[i]][0];
        newCol = currentCol + directions[dirOrder[i]][1];
        
        // Check if the new position is valid and not a wall
        if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && 
            maze[newRow][newCol] != '#') {
            
            // Additional check to avoid immediate backtracking
            if (maze[newRow][newCol] != 'X' || 
                (newRow == startRow && newCol == startCol)) {
                
                // Recursive call to continue traversal
                mazeTraverse(maze, newRow, newCol, startRow, startCol, visited + 1);
                moved = 1;
            }
        }
    }
    
    // If no move was possible and we're not at exit/start, we're stuck
    if (!moved && !(currentRow == 0 || currentRow == SIZE-1 || 
                   currentCol == 0 || currentCol == SIZE-1) &&
        !(currentRow == startRow && currentCol == startCol)) {
        printf("Stuck at position (%d, %d)\n", currentRow, currentCol);
    }
}

// Function to print the maze
void printMaze(char maze[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%c ", maze[i][j]);
        }
        printf("\n");
    }
}