MazePath.h:

#include

#include

#ifndef MAZEPATH_H

#define MAZEPATH_H

class MazePath {

public:

const static std::string DIRECTIONS;

const static std::string COMPLEMENTS;

//CONSTRUCTORS

MazePath();

MazePath(std::string steps);

//takes a step further into the maze

void takeStep(char step);

//returns the sequence of steps to get back to the starting point

std::string directionsOut();

//overloaded output operator

friend std::ostream& operator

// overloaded assignment operator

MazePath& operator= (const std::string &m);

private:

std::stack path;

std::string strPath;

};

#endif

MazePath.cxx

#include "MazePath.h"

#include

#include

#include

using namespace std;

const string MazePath::DIRECTIONS = "NSEW";

const string MazePath::COMPLEMENTS = "SNWE";

MazePath::MazePath() {

}

MazePath::MazePath(string steps) {

for (int ndx = 0; ndx

assert(DIRECTIONS.find(steps[ndx]) != string::npos);

path.push(steps[ndx]);

strPath.push_back(steps[ndx]);

}

}

//takes a step further into the maze

void MazePath::takeStep(char step) {

if (DIRECTIONS.find(step) != string::npos) {

path.push(step);

strPath.push_back(step);

}

}

//returns the sequence of steps to get back to the starting point

string MazePath::directionsOut() {

//your code here

return "";

}

//overloaded output operator

ostream& operator

//your code here

return out;

}

// overloaded assignmet operator

MazePath& MazePath::operator= (const string &m)

{

MazePath mp(m);

*this = mp;

return *this;

}

MazePathTest.cpp

#include "MazePath.h"

#include

#include

using namespace std;

int main ()

{

//Testing isValid function with valid strings

cout

MazePath m("NEEESW");

assert(m.directionsOut() == "ENWWWS" && "NEEESW should give result ENWWWS");

m = "W";

assert(m.directionsOut() == "E");

m = "S";

assert(m.directionsOut() == "N");

m = "N";

assert(m.directionsOut() == "S");

m = "E";

assert(m.directionsOut() == "W");

m = "EEEEEEEE";

assert(m.directionsOut() == "WWWWWWWW");

m = "WWWWWWWW";

assert(m.directionsOut() == "EEEEEEEE");

cout

}

Maze.h

#include

#ifndef MAZE_H

#define MAZE_H

class Maze

{

public:

static const char EMPTY = '.';

static const char BLOCKED = 'X';

static const char START = 'S';

static const char END = 'G';

// Creates a Maze with no blocked cells; start = (0, 0); goal = (SIZE, SIZE)

Maze();

// Puts obstacle on the cell (row, col)

void blockCell(int row, int col);

// is position (row, col) clear?

bool isClear(int row, int col) const;

// returns the size of the Maze

int size() const;

// clear the maze: erase all obstacles

void clearAllCells();

// sets the end cell to (col, row)

void setEndCell(int row, int col);

// sets the start cell to (col, row)

void setStartCell(int row, int col);

// find a path from S to G by backtracking

std::string solveBacktracking();

// overloaded output operator

friend std::ostream& operator

private:

static const int SIZE = 7;

char maze[SIZE][SIZE];

int startCellRow, endCellRow, startCellCol, endCellCol;

};

#endif // MAZE_H

Maze.cxx:

#include "Maze.h"

#include

using namespace std;

// Creates a Maze with no blocked cells; start = (0, 0); goal = (SIZE, SIZE)

Maze::Maze(){

for (int row = 0; row

for (int col = 0; col

maze[row][col] = EMPTY;

}

}

startCellRow = startCellCol = 0;

endCellRow = endCellCol = SIZE-1;

setStartCell(0,0);

setEndCell(SIZE-1, SIZE-1);

}

// Puts obstacle on the cell (row, col)

void Maze::blockCell(int row, int col){

maze[row][col] = BLOCKED;

}

// Sets start cell to (row, col)

void Maze::setStartCell(int row, int col){

maze[startCellRow][startCellCol] = EMPTY;

startCellRow = row;

startCellCol = col;

maze[startCellRow][startCellCol] = START;

}

// Sets goal cell to (row, col)

void Maze::setEndCell(int row, int col){

maze[endCellRow][endCellCol] = EMPTY;

endCellRow = row;

endCellCol = col;

maze[endCellRow][endCellCol] = END;

}

// is position (row, col) clear?

bool Maze::isClear(int row, int col) const{

return maze[row][col] == EMPTY;

}

// returns the size of the Maze

int Maze::size() const{

return SIZE;

}

// clear the maze: erase all obstacles

void Maze::clearAllCells(){

for (int row = 0; row

for (int col = 0; col

if (maze[row][col]!= 'S' || maze[row][col]!= 'G')

maze[row][col] = EMPTY;

}

}

}

// overloaded output operator

std::ostream& operator

for (int row = 0; row

for (int row = 0; row

out

for (int col = 0; col

out

}

out

}

for (int row = 0; row

return out;

}

std::string solveBacktracking(){

//your code here

return "";

}

Navigating a Maze Finding a path Assume that we have not been given the steps that the robot took to go inside a maze and we are left with the task of getting the robot out of the maze We can generalize this problem as finding a path from a start position to a goal position in a maze. A simple solution will simply have the robot navigate through available paths in the maze until it finds its way to the goal state, backtracking when it gets stuck. A backtracking algorithm for such solution is the following 1. Mark every square in the maze as unvisited. 2. Create an empty stack (of maze positions) 3. Push the start positions onto the stack, and mark the start square as visited 4. If the stack is empty, you're done and the maze is unsolvable 5. Let T be the top item on the stack. If T is equal to the finish square, youre done and the stack contains a solution to the maze 6. If all squares adjacent to T(i.e. the squares up, down, right, or left from T) are either blocked or are marked visited already, pop T off the stack and go to step 4 7. Otherwise, select a square S that is adjacent to T, unvisited, and unblocked Mark S as visited and push its positions on the stack. Go to step 4