#include <stdio.h>
#define SIZE 12

void mazeTraverse(char maze_data[SIZE][SIZE], int currentRow, int currentCol, int startRow, int startCol, int visited);
void printMaze(char maze_data[SIZE][SIZE]);

int main(void) {
    // Initialize all rows
    char maze_data[SIZE][SIZE] = {
        {'#','#','#','#','#','#','#','#','#','#','#','#'},
        {'#','.','.','.','#','.','.','.','.','.','.','#'},
        {'.','.','#','.','#','.','#','#','#','#','.','#'},
        {'#','#','#','.','#','.','.','.','.','#','.','#'},
        {'#','.','.','.','.','#','#','#','.','#','.','.'},
        {'#','#','#','#','.','#','.','#','.','#','.','#'},
        {'#','.','.','#','.','#','.','#','.','#','.','#'},
        {'#','#','.','#','.','#','.','#','.','#','.','#'},
        {'#','.','.','.','.','.','.','.','.','#','.','#'},
        {'#','#','#','#','#','#','.','#','#','#','.','#'},
        {'#','.','.','.','.','.','.','#','.','.','.','#'},
        {'#','#','#','#','#','#','#','#','#','#','#','#'}
    };
    
    int startRow = 2, startCol = 0;

    puts("Maze");
    printMaze(maze_data);
    puts(""); puts("Starting Maze Treversal");

    mazeTraverse(maze_data, startRow, startCol, startRow, startCol, 0);

    return 0;
}

void mazeTraverse(char maze_data[SIZE][SIZE], int currentRow, int currentCol, int startRow, int startCol, int visited) {
  if(!(currentRow == 0 || currentCol == 0) || visited > 0) {
    maze_data[currentRow][currentCol] = 'X';
  }

  printf("Step %d\n", visited++);
  printMaze(maze_data);
  puts("");

  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;
  }

  if (visited > 0 && currentRow == startRow && currentCol == startCol) {
    puts("No exit found!");
    return;
  }

  //RIGHT HAND RULE!
  //always turn right:
  int move = 0;
  int direct[4][2] = {{0, 1}, {1,0}, {0, -1}, {-1, 0}}; //Right, down, left, up
  int searchRow, searchCol;

  for(int i = 0; i < 4 && !move; i++) {
    int directOrder[4] = {0, 1, 2, 3}; //Right, down, left, up

    searchRow = currentRow + direct[directOrder[i]][0];
    searchCol = currentCol + direct[directOrder[i]][1];

    if (searchRow >= 0 && searchRow < SIZE && searchCol >= 0 && searchCol < SIZE && maze_data[searchRow][searchCol] != '#') {
      if (maze_data[currentRow][currentCol] != 'X' || (currentRow == startRow && currentCol == startCol)) {
        mazeTraverse(maze_data, searchRow, searchCol, startRow, startCol, visited+1);
        move = 1;
      }
    }
  }

  if (!move && !(currentRow == 0 || currentRow == SIZE-1 ||
                 currentCol == 0 || currentCol == SIZE-1) &&
      !(currentRow == startRow && currentCol == startCol)) {
    printf("Stuck at pos(%d, %d)\n", currentRow, currentCol);
  }
}

void printMaze(char maze_data[SIZE][SIZE]) {
  for(size_t i = 0; i < SIZE; i++) {
    for(size_t j = 0; j < SIZE; j++) {
      printf("%c\n", maze_data[i][j]);
    }
    puts("");
  }
}