// ----------------------------------------------------------
// Author: Alicia Thorsen
// File: maze_handout.c
// Date: 3/28/08
//
// Program traverses a maze recursively looking for an exit.
// ----------------------------------------------------------

#include <iostream>
#include <fstream>
using namespace std;

// Maze contents.
const char EXIT = 'E';
const char WALL1 = '|';
const char WALL2 = '-';
const char VISITED = '.';
const char OPEN = ' ';

// Maze Size.
const int ROWS = 10;
const int COLS = 13;

// Maze file.
const string MAZE_FILE = "maze.txt";

bool findPath(char [][COLS], int, int);

// ----------------------------------------------------------
// MAIN.
// ----------------------------------------------------------

int main() {
  ifstream in;
  char maze[ROWS][COLS], value;

  // Open maze file for reading.
  in.open(MAZE_FILE.c_str());
  if (in.fail()) {
    cout << "\nMaze file: " << MAZE_FILE << " not found. Aborting.\n";
    exit(1);
  }

  // Read in maze. Convert all visited spots to open.
  for (int i = 0; i < ROWS; ++i)
    for (int j = 0; j < COLS; ++j) {
      in >> value;
      if (value == VISITED)
        maze[i][j] = OPEN;
      else
        maze[i][j] = value;
    }

  // Find an exit from the given starting point.
  if (findPath(maze, 1, 0))
    cout << "\nExit found!\n\n";
  else
    cout << "\nNo exit found!\n\n";

  return 0;
}

// ----------------------------------------------------------
// bool findPath(char [][], int,int)
//
// Returns true if an exit can be found in the maze from the given starting
// point.
// ----------------------------------------------------------

bool findPath(char maze[][COLS], int row, int col){
  // Out Of Bounds.
  if ((row < 0) || (row >= ROWS) || (col < 0) || (col >= COLS))
    return false;

  // Check to see if we have found the exit.
  if (maze[row][col] == EXIT)
    return true;

  // Hit a Wall
  if ((maze[row][col] == WALL1) || (maze[row][col] == WALL2))
    return false;

  // We have been here before.
  if (maze[row][col] == VISITED)
    return false;

  // We will move here and explore further
  maze[row][col] = VISITED;

  // Up
  if (findPath(maze, row - 1, col))
    return true;
  
  // Left
  if (findPath(maze, row, col - 1))
    return true;

  // Down
  if (findPath(maze, row + 1, col))
    return true;

  // Right
  if (findPath(maze, row ,col + 1))
    return true;

  // No path can be found from here
  return false;
}