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