// Programmer:	Gregory A. Perkins
// Class:		CS 66
// Due:			8 April 1997

// This program prompts the user to enter dimensions for a maze, then prompts the
// user to enter the actual maze as a series of '.' and '*'.  '.' represents a
// passible cell within the maze, while '*' represents an impassible cell within the
// maze.  After the user enters the maze, the program then proceeds to check if the maze
// is actually solvable.  If the maze is solvable, the program will display the route
// it found through the maze.  If the maze is not solvable, the program will display the
// fact that 'NO PATH EXISTS!'

//*********************  MODIFICATIONS TO CODE  *****************************************
//  Created PathFinder.cpp which contains the main() && recursive portion of program
//  Created implementations of Maze::is_open() && Maze::unmark()
//***************************************************************************************

#include 
#include "maze.h"

//==============================> Function Prototypes <=================================
char GetChoice();
// POST:  FCTVAL == character(s) entered by the user

void GetDimensions(int& r, int& c);
// PRE:  assigned (r && c)
// POST:  assigned user entered values (r && c)

void InputMaze(int r, int c, Maze& l);
// PRE:  assigned (r && c)  &&
//		 assigned (Maze l) of size r rows and c columns
// POST:  all valid cells (r, c) contain '.' or '*' as
// 		  entered by the user

void PathFinder(int r, int c, Maze& l, char mark, Boolean& found);
// PRE:  assigned (r && c) &&
//    	 assigned (Maze l) &&
//		 assigned (mark && found)
// POST:  if path through maze exists, found == TRUE &&
//		  the path has been marked
//		  else, found == FALSE

int main()
{
	char choice = 'Y';			// allows initial entry into the loop
	int rows;					// number of rows for intended maze
	int cols;					// number of columns for intended maze
	char flag = 'a';			// initialize value of maze route marker
	
	while (choice == 'Y' || choice == 'y')
	{
		Boolean pathFound = FALSE;	// boolean variable indicating whether route has been found
		
		GetDimensions(rows, cols);	// user enters the size of the maze
		
		Maze lab(rows, cols);		// maze of size rows && columns is created
		
		InputMaze(rows, cols, lab);	// user enters the actual "test" maze
		
		int startRow = 1;		// row to start searching
		int startCol = 1;		// column to start searching
		PathFinder(startRow, startCol, lab, flag, pathFound);  // computer searches for path
		
		if (pathFound)			// if maze is solvable
		{
			cout << lab			// output the solution
				 << endl;
		}
		else
		{
			cout << "NO PATH EXISTS!"		// inform user that maze is not solvable
				 << endl;
		}
		
		choice = GetChoice();					// user prompted for decision to continue
	}
	
	return (1);
}

//==============================> Function Definitions <================================

//==============================> GetChoice <===========================================
char GetChoice()
// POST:  FCTVAL == character(s) entered by the user
{
	char ch;							// value to hold character entered by user
	
	cout << "Continue? (Y or N): ";
	cin >> ch;
	cout << endl;

	cin.ignore(50, '\n');				// stream clean up
	
	return (ch);						// return character entered by user
}

//==============================> GetDimensions <=======================================
void GetDimensions(int& r, int& c)
// PRE:  assigned (r && c)
// POST:  assigned user entered values (r && c)
{
	cout << "Enter number of rows desired (MAX = 25): ";
	cin >> r;
	cout << "Enter number of columns desired (MAX = 25): ";
	cin >> c;
	cout << endl;
	
	cin.ignore(50, '\n');				// stream clean up
	
	return;
}

//==============================> Input Maze <==========================================
void InputMaze(int r, int c, Maze& l)
// PRE:  assigned (r && c)  &&
//		 assigned (Maze l) of size r rows and c columns
// POST:  all valid cells (r, c) contain '.' or '*' as
// 		  entered by the user
{
	cout << "Specify maze as "
		 << r
		 << " lines of "
		 << c
		 << " chars ('.' or '*'): "
		 << endl;
		 
	cin >> l;				// use of overloaded operator to fill in maze
	cout << endl;
	
	return;
}

//=============================> PathFinder <===========================================
void PathFinder(int r, int c, Maze& l, char mark, Boolean& found)
// PRE:  assigned (r && c) &&
//    	 assigned (Maze l) &&
//		 assigned (mark && found)
// POST:  if path through maze exists, found == TRUE &&
//		  the path has been marked
//		  else, found == FALSE
{
	if (l.is_open(r, c))							// only continue if cell is open
	{
		l.mark(r, c, mark);
		
		if (r == l.max_row() && c == l.max_col())	// if this cell is the bottom right(exit)
		{
			found = TRUE;							// then a path has been found
			return;
		}
		
		mark++;				// set next marker value for subsequent calls
		if (mark > 'z')		// if last marker value reached
			mark = 'a';		// start value at 'a' again
			
		if (c < l.max_col())
		{
			PathFinder(r, c+1, l, mark, found);		// check cell to the right
			if (found)								// if path found stop checking
				return;
		}

		// ASSERT:  found == FALSE
		if (r < l.max_row())
		{
			PathFinder(r+1, c, l, mark, found);		// check cell below
			if (found)								// if path found stop checking
				return;
		}

		// ASSERT:  found == FALSE
		if (c > 1)
		{
			PathFinder(r, c-1, l, mark, found);		// check cell to the left
			if (found)								// if path found stop checking
				return;
		}

		// ASSERT:  found == FALSE
		if (r > 1)
		{
			PathFinder(r-1, c, l, mark, found);		// check cell above
			if (found)								// if path found stop checking
				return;
		}
		
		// ASSERT:  found == FALSE
		l.unmark(r, c);
	}
	else											// if cell is impassible
		return;
}