/*
 * This program reads a maze from the file text file specified by the user.
 * It then then finds and displays the shortest path from the starting
 * position in the maze to the goal.
 *
 * Written by: Carl Sable
 */

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

#define NUMROWS 10
#define NUMCOLS 10
#define INFINITY 999999 // Semi-arbitrary large value

int read_maze(char *, char [NUMROWS][NUMCOLS], int *, int *);
void display_maze(char [NUMROWS][NUMCOLS]);
void copy_maze(char [NUMROWS][NUMCOLS], char[NUMROWS][NUMCOLS]);
void solve_maze(char [NUMROWS][NUMCOLS], int, int, int);

char mazeBest[NUMROWS][NUMCOLS]; // Stores the best path to goal found so far
int lengthBest = INFINITY; // Stores the length of the best path found so far

int main(void)
{
  char maze[NUMROWS][NUMCOLS]; // Stores the maze
  int startRow, startCol; // The starting point in the maze
  char mazeFilename[40]; // The name of the maze file

  printf("Enter the name of the textfile containing the maze: ");
  scanf("%39s", mazeFilename);
  while (getchar() != '\n');

  if (!read_maze(mazeFilename, maze, &startRow, &startCol)) {
    printf("Error reading maze from %s!\n", mazeFilename);
    return 1;
  }

  printf("Starting maze:\n");
  display_maze(maze);

  solve_maze(maze, startRow, startCol, 0);
  
  if (lengthBest == INFINITY) {
    printf("\nNo path to the goal was found in maze!\n");
    return 0;
  }
  else {
    printf("\nBest solution found:\n");
    display_maze(mazeBest);
  }

  return 0;
}

/* 
 * Read maze from the specified file.
 * Fill in *sRow and *sCol with position of 'O'.
 * If error, return 0 (false), else return 1 (true).
 */
int read_maze(char *fn, char maze[NUMROWS][NUMCOLS], int *sRow, int *sCol)
{
  FILE *fpMaze;
  int row, col;

  /* Open maze text file, make sure it opens OK. */
  if ((fpMaze = fopen(fn, "r")) == NULL)
    return 0;

  /* Loop through the rows. */
  for (row = 0; row < NUMROWS; row++) {
    /* Loop through the column in current row. */
    for (col = 0; col < NUMCOLS; col++) {
      maze[row][col] = getc(fpMaze);
      /* Check if this is the starting position. */
      if (maze[row][col] == 'O') {
	*sRow = row;
	*sCol = col;
      }
    }
    /* Ignore newline at end of each row. */
    getc(fpMaze);
  }

  return 1;
}

/* Display the maze passed as a parameter to standard output. */
void display_maze(char maze[NUMROWS][NUMCOLS])
{
  int row, col;

  for (row = 0; row < NUMROWS; row++) {
    for (col = 0; col < NUMCOLS; col++)	{
      putchar(maze[row][col]);
    }
    putchar('\n');
  }

  return;
}

/* Copy the maze in mazeSrc to mazeDest. */
void copy_maze(char mazeSrc[NUMROWS][NUMCOLS], 
	       char mazeDest[NUMROWS][NUMCOLS])
{
  int row, col;

  for (row = 0; row < NUMROWS; row++) {
    for (col = 0; col < NUMCOLS; col++) {
      mazeDest[row][col] = mazeSrc[row][col];
    }
  }

  return;
}

/*
 * Given:
 *    (1) The maze with the path so far filled in
 *    (2) The current row 
 *    (3) The current column
 *    (4) The length of the path so far
 * The function solve_maze recursively tries to solve the maze.
 * 
 * When a solution is found, the function compares it to the previous best
 * solution found so far, and if the new solution is better, it updates
 * the appropriate globals to store the new solution and its length.
 */
void solve_maze(char mazeCur[NUMROWS][NUMCOLS],
		int curRow,
		int curCol,
		int length)
{
  // Display updated maze
  system("clear");
  display_maze(mazeCur);
 
  // If path is already as long as the best solution found so far,
  // there is no need to look further
  if (length >= lengthBest)
    return;

  // Check if a solution has been found
  if ((mazeCur[curRow-1][curCol] == 'X') ||
      (mazeCur[curRow+1][curCol] == 'X') ||
      (mazeCur[curRow][curCol+1] == 'X') ||
      (mazeCur[curRow][curCol-1] == 'X')) {
    // Found solution, better then previous best, update globals
    lengthBest = length;
    copy_maze(mazeCur, mazeBest);
    return;
  }

  // Recurse in each possible direction that is empty
  // (This is not the only way to go about this)
  if (mazeCur[curRow-1][curCol] == ' ') {
    mazeCur[curRow-1][curCol] = 'O';
    solve_maze(mazeCur, curRow-1, curCol, length+1);
    mazeCur[curRow-1][curCol] = ' ';
  }
  if (mazeCur[curRow+1][curCol] == ' ') {
    mazeCur[curRow+1][curCol] = 'O';
    solve_maze(mazeCur, curRow+1, curCol, length+1);
    mazeCur[curRow+1][curCol] = ' ';
  }
  if (mazeCur[curRow][curCol-1] == ' ') {
    mazeCur[curRow][curCol-1] = 'O';
    solve_maze(mazeCur, curRow, curCol-1, length+1);
    mazeCur[curRow][curCol-1] = ' ';
  }
  if (mazeCur[curRow][curCol+1] == ' ') {
    mazeCur[curRow][curCol+1] = 'O';
    solve_maze(mazeCur, curRow, curCol+1, length+1);
    mazeCur[curRow][curCol+1] = ' ';
  }

  return;
}