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 <iostream>
#include <fstream>
#include <string>
#include <vector>
#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\n";
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 <iostream>

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