Answered step by step
Verified Expert Solution
Question
1 Approved Answer
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
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
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 }
for (int row = 0; row
return out;
}
std::string solveBacktracking(){
//your code here
return "";
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started