Project 4: Maze Solver

The purpose of this assignment is to assess your ability to:

• Implement stack and queue abstract data types
• Utilize stack and queue structures in a computational problem.

This assignment reinforces competency 6.1: Select and utilize data structures appropriate to a given computational problem.

For this project, implement a stack and a queue data structure. After testing the class, complete the depth-first search method (provided). The method should indicate whether or not a path was found, and, in the case that a path is found, output the sequence of coordinates from start to end.

The following code and related files are provided. Carefully ready the code and documentation before beginning.

• A MazeCell class that models a cell in the maze. Each MazeCell object contains data for the row and column position of the cell, the next direction to check, and a bool variable that indicates whether or not the cell has already been visited.
• A Source file that creates the maze and calls your depth-first search method.
• An input file, maze.in, that may be used for testing.

You will write the following:

• a generic stack class, called MyStack, that supports the provided API (see file stackAPI.png)
• a generic queue class, called MyQueue, that supports the provided API (see file queueAPI.png)
• an implementation for the depth-first algorithm

Create a Loom video with a length of 5 minutes or less in which you run your code and comment on the following:

• Your data structure choices for the stack and queue implementation.
• Your use of MyStack and MyQueue structures in your maze solution
• Your depth first algorithm

Submit the following:

• A zip file with your code

------------------

//Source for MazeSolver

#include #include #include #include #include "myStack.h" #include "MyQ.h" #include "MazeCell.h"

using namespace std;

#define NORTH 0 #define EAST 1 #define SOUTH 2 #define WEST 3 #define DONE 4 #define SUCCESS 10 #define FAILURE 20

//method headers*******************************************************

//depthFirst header void depthFirst(MazeCell start, MazeCell end);

//global variables*****************************************************

//# rows and cols in the maze int rows, cols; //pointer to the grid (2-d array of ints) int** grid; //pointer to the maze cells (2-d array of MazeCell objects) MazeCell** cells;

int main() { //create the Maze from the file ifstream fin("maze.in"); if(!fin){ cout << "File not found "; exit(2); }

//read in the rows and cols fin >> rows >> cols;

//create the maze rows grid = new int* [rows]; //add each column for (int i = 0; i < rows; i++) grid[i] = new int[cols];

//read in the data from the file to populate for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { fin >> grid[i][j]; } }

//look at it for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == 3) cout << "S" << " "; else if (grid[i][j] == 4) cout << "E" << " "; else cout << grid[i][j] << " "; } cout << endl; }

//make a 2-d array of cells cells = new MazeCell * [rows]; for (int i = 0; i < rows; i++) { cells[i] = new MazeCell[cols]; }

//all MazeCell in the cells grid has a default init //only update those cells that are not walls

MazeCell start, end; //iterate over the grid for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] != 0) { cells[i][j].setCoordinates(i, j); //look for the start and end cells if (grid[i][j] == 3) start = cells[i][j]; if (grid[i][j] == 4) end = cells[i][j]; }

} } //testing cout <<"start: "<< start << " end: " << end << endl; //solve it! depthFirst(start, end);

return 0; }

//this function should find a path through the maze //if found, output the path from start to end //if not path exists, output a message stating so

void depthFirst(MazeCell start, MazeCell end) {

-------------

/* * * CST-201, Maze Solver Project * Provided starter code * MazeCell class * DO NOT CHANGE THIS FILE * */

#ifndef MAZECELL_H #define MAZECELL_H

#include

using namespace std;

//models an open cell in a maze //each cell knows its coordinates (row, col), //direction keeps track of the next unchecked neighbor. //a cell is considered 'visited' once processing moves to a neighboring cell //the visited variable is necessary so that a cell is not eligible for visits //from the cell just visited

class MazeCell { private:

int row, col; //direction to check next //0: north, 1: east, 2: south, 3: west, 4: complete int direction; bool visited;

public: //set row and col with r and c MazeCell(int r, int c) { row = r; col = c; direction = 0; visited = false; }

//no-arg constructor MazeCell() { row = col = -1; direction = 0; visited = false; }

//copy constructor MazeCell(const MazeCell& rhs) { this->row = rhs.row; this->col = rhs.col; this->direction = rhs.direction; this->visited = rhs.visited; }

int getDirection()const { return direction; }

//update direction. if direction is 4, mark cell as visited void advanceDirection() { direction++; if (direction == 4) visited = true; }

//change row and col to r and c void setCoordinates(int r, int c) { this->row = r; this->col = c; }

int getRow()const { return row; }

int getCol()const { return col; }

//cells are equal if they have the same row and col, respectively bool operator==(const MazeCell& rhs)const { return row == rhs.row && col == rhs.col; }

bool operator!=(const MazeCell& rhs)const { return !((*this) == rhs); }

//output cell as ordered pair friend ostream& operator<<(ostream& out, const MazeCell& rhs) { out << "(" << rhs.row << "," << rhs.col << ")"; return out; }

//set visited status to true void visit() { visited = true; }

//reset visited status void reset() { visited = false; }

//return true if this cell is unvisited bool unVisited()const { return !visited; }

//may be useful for testing, return string representation of cell string toString()const { string str = "(" + to_string(getRow()) + "," + to_string(getCol())+ ")"; return str; }

};

#endif

}

-----------------

4 6 1 1 3 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 4 0