[Repost] Do not Copy from other posts! Fill in only the missing code for the fun
ID: 3910973 • Letter: #
Question
[Repost] Do not Copy from other posts!
Fill in only the missing code for the function vector<int> maze::bfs() in the maze.cpp file. Do not add any other lines of code that wasn't defined in the maze.h file.
The appropriate mathematical model for a general maze: an undirected graph with a start node and an exit node
The goal is to find a path from the start to the exit
We can use either of the graph traversal algorithms covered previously
depth-first search; and
breadth-first search
The only difference is that we discontinue the search if we discover the exit vertex
In our model, we will just return the predecessor array, which can the be used to print the exit path
Rather than using a separate Graph class, we build in the adjacency lists as part of the MazeGraph class
The size attribute of the class holds the number of vertices
The vertices are then the integers 0, 1, …, size-1
We define a node type – vnode – that holds a vertex and a next pointer
We will use a vector<vnode *> to hold the adjacency lists
Thus, adjList[i] will be a pointer to the first node of the adjacency list for vertex i
// ------------------------------maze.h----------------------------
#include<stack>
#include<queue>
#include<vector>
using namespace std;
struct vnode {
int v; // vertex
vnode *next;
vnode(int u, vnode *n) {v=u; next=n;}
};
typedef vnode * vnodeptr;
class maze
{
public:
maze(); // interactive constructor using cin
void print_dfs_exitpath();
void print_bfs_exitpath();
private:
int size;
int start;
int exit;
vector<vnodeptr> adjList;
stack<int> dfs();
vector<int> bfs();
};
void printBottomToTop(stack<int> S);
void printPredecessorPath(vector<int> pred);
// ------------------------------maze.cpp----------------------------
#include "maze.h"
#include <cassert>
#include <iostream>
using namespace std;
void printBottomToTop(stack<int> S)
{
stack<int> tmp;
while(!S.empty()) {
tmp.push(S.top());
S.pop();
}
while(!tmp.empty()) {
cout << tmp.top();
tmp.pop();
if(!tmp.empty())
cout << "->";
else
cout << endl;
}
}
void printPredecessorPath(vector<int> pred,int target)
{
stack<int> S;
int current = target;
while(pred[current] >= 0) {
S.push(current);
current = pred[current];
}
while(S.size() > 1) {
cout << S.top() << "->";
S.pop();
}
cout << S.top() << endl;
}
maze::maze()
{
int vertex;
cin >> size;
cin >> start;
cin >> exit;
assert(0 <= start && start < size);
assert(0 <= exit && exit < size);
adjList.resize(size,NULL);
for(int i = 0; i < size; ++i) {
cin >> vertex;
while(vertex != -1) {
if(vertex == i) {
cerr << "Invalid adjacency; terminating" << endl;
assert(vertex != i);
}
adjList[i] = new vnode(vertex,adjList[i]); // insert at begining
cin >> vertex;
}
}
}
stack<int> maze::dfs() // depth-first search
{
int current, nbr;
vector<bool> visited(size,false);
stack<int> path;
visited[start] = true;
path.push(start);
while(!path.empty()) {
current = path.top();
if(current == exit) {
break;
}
vnodeptr cursor = adjList[current];
while(cursor != nullptr && visited[cursor->v])
cursor = cursor->next;
if(cursor != nullptr) { // found an open neighbor
nbr = cursor->v;
visited[nbr] = true;
path.push(nbr);
} else { // back out
path.pop();
if(path.empty()) { // backed out from start
break;
}
}
// Continue search from the newly discovered vertex
}
return path;
}
void maze::print_dfs_exitpath()
{
stack<int> path = dfs();
if(path.empty())
cout << "No way out" << endl;
printBottomToTop(path);
}
void maze::print_bfs_exitpath()
{
vector<int> pred = bfs();
if (pred[exit] == -1)
cout << "No way out" << endl;
else
printPredecessorPath(pred,exit);
}
vector<int> maze::bfs() // breadth-first search
{
int current = start, nbr;
queue<int> Q;
vector<int> pred(size,-1);
pred[start] = -2;
Q.push(start);
while(!Q.empty()) {
current = Q.front();
Q.pop();
// Fill in the missing code
}
return pred;
}
// ------------------------------ test_mazedfs.cpp----------------------------
// Used to test print_dfs_exitpath()
#include <iostream>
#include "maze.h"
using namespace std;
int main()
{
maze RatHaus;
RatHaus.print_dfs_exitpath();
cout << endl;
return 0;
}
// ------------------------------RescueRemy.cpp-----------------------------
// This program should always be run with input redirected to a file
// Use this to test your print_bfs_exitpath method
#include <iostream>
#include "maze.h"
using namespace std;
int main()
{
maze RatHaus; // interactive constructor
RatHaus.print_bfs_exitpath();
cout << endl;
return 0;
}
Test Input and Correct Output
Note: the order of the vertices in the adjacency lists will be the reverse of the order in which they appear in the input file because they are inserted at the front of the list.
Input:
6
2
3
2 3 5 -1
2 3 4 5 -1
0 1 4 5 -1
0 1 5 -1
1 2 5 -1
0 1 2 3 4 -1
Correct Output
2 5 3
Explanation / Answer
//RescueRemy.cpp
#include "Position.h"
#include "Maze.h"
#include "PrintMacros.h"
int main(void) {
// Variable for maze size
int maze_size;
// Display welcome message & instructions
printx("Welcome to the Rat in the Maze program, where we will find a ");
printx("path from the start cell to the end cell of a maze so that Remy ");
printx("may escape. You will first enter the data specifying the maze. ");
printx("After that, if escape is possible, we show an escape path using ");
printx("DFS and then a shortest possible path. ");
// Prompt for & input maze size
printx(" Enter the size (number of rows and columns of the square maze): ");
std::cin >> maze_size;
println(2);
// Build maze
Maze RatHaus1(maze_size + 2);
RatHaus1.initialize();
Maze RatHaus2(RatHaus1);
// Display maze
println(2, "Constructed Maze:", 2);
RatHaus1.display(std::cout);
// Get/Display DFS exit path
RatHaus1.print_dfsExitPath();
println();
// Get/Display BFS (shortest) exit path
RatHaus2.printShortestPath();
println();
return 0;
}
----------------------------------------------------------------------------------------------------
//Maze.cpp
#include <cstdlib>
#include <cassert>
#include "Maze.h"
#include "PrintMacros.h"
Maze::Maze() {
size = MAZEMAX;
start = Position(1, 1); // Upper left corner position
exitpos = Position(MAZEMAX - 2, MAZEMAX - 2); // lower right corner position
M = getMazeArray(size);
for (std::size_t i {0}; i < size; i++) {
for (std::size_t j {0}; j < size; j++) {
M[i][j] = WALL;
}
}
}
// Construct Maze - Input Size (max)
Maze::Maze(std::size_t max) {
size = max;
start = Position(1, 1);
exitpos = Position(size - 2, size - 2);
M = getMazeArray(size);
for (std::size_t i {0}; i < size; i++) {
for (std::size_t j {0}; j < size; j++) {
M[i][j] = WALL;
}
}
}
// Construct Maze from Another (Copy Constructor)
Maze::Maze(const Maze &other):
size(other.size), start(other.start), exitpos(other.exitpos) {
M = getMazeArray(size);
for(std::size_t i {0}; i < size; i++) {
for (std::size_t j {0}; j < size; j++) {
M[i][j] = other.M[i][j];
}
}
}
// Destructor - Deallocate maze array
Maze::~Maze() {
for(std::size_t i {0}; i < size; ++i) {
delete []M[i];
}
delete []M;
}
/* Maze Functions: */
/*
* print_dfsExitPath - Uses depth first search to find an exit path out of the maze.
* Prints the path, if found.
*/
void Maze::print_dfsExitPath() {
// S - holds the coordinates exit path
// current/adj - holds the current position/adjacent positions
std::stack<Position> S;
Position current, adj;
// Push the starting position onto stack and set state
S.push(start);
setState(start, VISITED);
// Iterate while stack is not empty or exit position has not been found
while (!S.empty() && !((current = S.top()) == exitpos)) {
Direction d {DOWN};
// Check adjacent cells for open position. When an open position is found, push it onto the stack
while (d != NONE) {
if (getState((adj = current.Neighbor(d))) == OPEN) {
setState(adj, VISITED);
S.push(adj);
break;
} else d = next_direction(d);
}
// If no adjacent open positions were located, pop the current position off the stack
// Otherwise, we transverse the maze deeper
if (d == NONE) S.pop();
}
// Print the exit path if one was found. Otherwise, print no path message
if (S.size()) {
std::stack<Position> tmp = S, S2;
while (!tmp.empty()) {
S2.push(tmp.top());
tmp.pop();
}
printx("Remy, here is a sequence of positions to escape the maze: ");
printStackPath(S);
println(2);
display_exit_path(std::cout, S2);
} else printx("Oh no, Poor Remy! There is now way to escape from the maze. ");
}
/*
* printShortestPath - Uses breadth first search to find the shortest exit path of the of maze.
* Prints the path, if found.
*/
void Maze::printShortestPath() {
// Q - holds positions to be checked for open adjacent positions
std::queue<Position> Q;
// Initialize predecessor array
Position **predecessor = new Position *[size];
for(int i {0}; i < size; ++i) {
predecessor[i] = new Position[size];
for(int j {0}; j < size; ++j) {
predecessor[i][j] = NULLPOS;
}
}
// Push the starting position onto queue and set state
Q.push(start);
setState(start, VISITED);
// Starting with front of the queue, iterate until the queue is empty
for (Position current {Q.front()}, adj; !Q.empty(); Q.pop(), current = Q.front()) {
// Check adjacent cells for openings.
// When an open position is found, push it onto the queue and set state/predecessor array accordingly
for (Direction d {DOWN}; d != NONE; d = next_direction(d)) {
if (getState((adj = current.Neighbor(d))) == OPEN) {
predecessor[adj.getRow()][adj.getCol()] = current;
Q.push(adj);
setState(adj, VISITED);
}
}
}
// Print the shortest path if an exit path was found. Otherwise print no path message
if (predecessor[exitpos.getRow()][exitpos.getCol()] != NULLPOS) {
printx("Remy, here is a shortest sequence of positions to escape the maze: ");
display_shortest_exit_path(std::cout, predecessor);
} else printx("Oh no, Poor Remy! There is now way to escape from the maze. ");
}
/*
* Get Maze Array - Attempt to allocate array for maze
*/
State **getMazeArray(std::size_t size) {
State **A;
try {
A = new State *[size];
} catch(std::bad_alloc) {
printx("Unable to allocate array of state pointers. ", std::cerr);
exit(1);
}
for(std::size_t i {0}; i < size; i++) {
try {
A[i] = new State[size];
} catch (std::bad_alloc) {
printx("Unable to allocate row of state values. ", std::cerr);
exit(1);
}
}
return A;
}
/*
* Maze Obj Overloaded Assignment Operator
*/
Maze& Maze::operator=(const Maze &origMaze) {
if (size != origMaze.size) {
State **hold = M;
size = origMaze.size;
M = getMazeArray(size);
delete []hold;
}
for(std::size_t i {0}; i < size; i++) {
for (std::size_t j {0}; j < size; j++) {
M[i][j] = origMaze.M[i][j];
}
}
return *this;
}
/*
* Initialize Maze - Input start/exit positions & open positions and initialize maze
*/
void Maze::initialize() {
printx(" Enter the start position ");
std::cin >> start;
printx(" Enter the exit position ");
std::cin >> exitpos;
printx(" For each row, enter the column indexes of the open positions, ");
printx("separated by spaces and terminated by an entry of 0 ");
for (std::size_t i {1}, j; i < size-1; i++) {
printx(" row " << i << ": ");
std::cin >> j;
while (j > 0){
M[i][j] = OPEN;
std::cin >> j;
};
}
if (getState(start) != OPEN) M[start.getRow()][start.getCol()] = OPEN;
}
/*
* Get State - Get state of specified maze position
*/
State Maze::getState(const Position &P) const {
return M[P.getRow()][P.getCol()];
}
/*
* Set State - Set state of specified maze position
*/
void Maze::setState(const Position &P, State s) {
std::size_t i = P.getRow();
std::size_t j = P.getCol();
assert(1 <= i && i <= size && 1 <= j && j <= size);
M[i][j] = s;
}
/*
* Display Maze - Print maze to provided output stream
*/
void Maze::display(std::ostream &out) const {
for (std::size_t i {0}; i < size; ++i) {
for (std::size_t j {0}; j < size; ++j) {
printx(((Position(i,j) == start && start == exitpos) ? 'b'
: (Position(i,j) == start) ? 's'
: (Position(i,j) == exitpos) ? 'e'
: (M[i][j] == WALL) ? '*' : '|') , out);
printx(((j+1 == size ? (i+1 == size ? " " : " ") : "")), out);
}
}
}
/*
* Display Exit Path - Displays the maze with the exit path found via DFS
*/
void Maze::display_exit_path(std::ostream &out, std::stack<Position> path) const {
// Allocate a temp. 2D array to hold maze display. Assign maze display like above display function
char **maze = new char *[size + 1];
for (std::size_t i {0}; i < size; ++i) {
maze[i] = new char[size];
for (std::size_t j {0}; j < size; ++j) {
maze[i][j] = (Position(i, j) == start && start == exitpos) ? 'b' :
(Position(i, j) == start) ? 's' :
(Position(i, j) == exitpos) ? 'e' :
(M[i][j] == WALL) ? '*' : '|';
}
maze[i][size] = ' ';
}
// Use the exit path held in stack parameter to build a maze display with the exit path
Position current, adj;
while (!path.empty()) {
current = path.top();
path.pop();
// Overwrite open positions in path with corresponding arrow char. Don't overwrite start/exit position characters ('s'/'e')
if (current != start && current != exitpos) {
adj = path.top();
maze[current.getRow()][current.getCol()] = (current.Neighbor(DOWN) == adj) ? 'v' :
(current.Neighbor(UP) == adj) ? '^' :
(current.Neighbor(RIGHT) == adj) ? '>' : '<';
}
}
// Output maze display to provided output stream
for (int i {0}; i < size; ++i) {
printx(maze[i], out);
}
printx(' ', out);
// Delete tmp maze display
delete[] maze;
}
/*
* Display Shortest Exit Path - Displays the maze with the shortest exit path found via BFS
*/
void Maze::display_shortest_exit_path(std::ostream &out, Position **pred) const {
// Allocate a temp. 2D array to hold maze display. Assign maze display like above display function
char **maze = new char *[size + 1];
// Build the maze display based on type of each position
for (std::size_t i {0}; i < size; ++i) {
maze[i] = new char[size];
for (std::size_t j {0}; j < size; ++j) {
maze[i][j] = (Position(i, j) == start && start == exitpos) ? 'b' :
(Position(i, j) == start) ? 's' :
(Position(i, j) == exitpos) ? 'e' :
(M[i][j] == WALL) ? '*' : '|';
}
maze[i][size] = ' ';
}
// Print the exit path coordinates and add exit path to maze display using predessecor array
printPredecessorPath(pred, exitpos, maze);
// Print maze display to provided stream
printx(" ", out);
for (std::size_t i {0}; i < size; ++i) {
printx(maze[i], out);
}
printx(' ', out);
// Delete maze display
delete[] maze;
}
/*
* Print Stack Path - Print the exit path coordinates from stack param obtained via DFS
*/
void Maze::printStackPath(std::stack<Position> S) const {
if (S.empty()) {
return;
}
Position target = S.top();
S.pop();
printStackPath(S);
printx(target << " ");
}
/*
* Print Predecessor Path - Print the shortest exit path coordinates from predecessor param obtained via BFS
*/
void Maze::printPredecessorPath(Position **pred, Position target, char **m) const {
// Base case - exit when target is nullpos
if (target == NULLPOS) {
return;
}
// Get position preceeding target position
Position p = pred[target.getRow()][target.getCol()];
// Using the target and predecessor positions, assign the corresponding path arrow to the maze display
if (target != start && target != exitpos) {
m[target.getRow()][target.getCol()] = (target.getCol() != p.getCol()) ? (target.getCol() - p.getCol() == 1 ? '>' : '<')
: (target.getRow() - p.getRow() == 1 ? 'v' : '^');
}
// Recursively print exit position coordinates / build maze exit display
printPredecessorPath(pred, p, m);
printx(target << " ");
}
-------------------------------------------------------------------------------------------------------------
//Maze.h
#ifndef __MAZE
#define __MAZE
#include "Position.h"
#include <stack>
#include <queue>
/*
* State enumeration - three possible states: open, visited, wall
*/
enum State {
OPEN,
WALL,
VISITED
};
/*
* Position object with values -1, -1. Represents a null position.
*/
const Position NULLPOS(-1, -1);
/*
* Allocates dynamic 2-d array of states having rows and coloumns of size. Returns pointer used to create array.
*/
State **getMazeArray(std::size_t size);
/*
* Maze class
*/
class Maze {
private:
/* Maze Size (row and column size) */
std::size_t size;
/* Maze Start Position & Exit Positions */
Position start, exitpos;
/* State Double Pointer - for 2-D array of maze state values */
State **M;
public:
/* Defualt Maze Size */
static const std::size_t MAZEMAX = 12;
/* Constructors */
Maze(); // Start set to upper left corner, exit to lower right corner, size to MAZEMAX
Maze(std::size_t n); // Start set to upper left corner, exit to lower right corner, size to n
Maze(Position s, Position e); // Start set to s, exit to e, size to MAZEMAX
Maze(std::size_t n, Position s, Position e); // Start set to s, exit to e, size to n
Maze(const Maze &other); // Copy constructor
/* Destructor */
~Maze();
/* Overloaded Assignment Operator */
Maze& operator=(const Maze &origMaze);
/* Initialize Maze */
void initialize();
/* Display Maze */
void display(std::ostream &out) const;
/* Get State of Position */
State getState(const Position &P) const;
/* Set State of Position - P must correspond to non-hedge position within maze */
void setState(const Position &P, State s);
/* Print DFS Exit Path - Uses DFS to find maze exit path */
void print_dfsExitPath();
/* Print BFS Exit Path - Uses BFS to find shortest maze exit path */
void printShortestPath();
/* Display DFS Exit Path - Displays the maze with the DFS exit path in 'path' para */
void display_exit_path(std::ostream &out, std::stack<Position> path) const;
/* Display BFS Exit Path - Prints the maze along with the BFS exit path in 'path' para */
void display_shortest_exit_path(std::ostream &out, Position **path) const;
/* Print Stack Path - Prints the maze's exit path coordinates obtained via DFS */
void printStackPath(std::stack<Position> S) const;
/* Print Predecessor Path - Prints the maze's shortest exit path coordinates obtained via BFS */
void printPredecessorPath(Position **pred, Position target, char **m) const;
};
#endif
--------------------------------------------------------------------------------------
//Position.cpp
#include "Position.h"
/*
* Get Next Direction (DOWN->LEFT->UP->RIGHT)
*/
Direction next_direction(Direction d) {
switch(d) {
case DOWN: return LEFT;
case LEFT: return UP;
case UP: return RIGHT;
default: return NONE;
}
}
/*
* Get Neighbor Position
*/
Position Position::Neighbor(Direction d) const {
switch(d) {
case DOWN: return Position(row + 1, col );
case LEFT: return Position(row, col - 1);
case UP: return Position(row - 1, col );
case RIGHT: return Position(row, col + 1);
default: abort();
}
}
/*
* Overloaded Equality Operator
*/
bool Position::operator==(const Position &other) const {
return row == other.row && col == other.col;
}
/*
* Overloaded Inequality Operator
*/
bool Position::operator!=(const Position &other) const {
return row != other.row || col != other.col;
}
/*
* Display Position Coordinates
*/
void Position::display(std::ostream & out) const {
out << '('<< row << ',' << col << ')';
}
/*
* Input Position Coordinates
*/
void Position::input(std::istream & in) {
std::cout << "row index: ";
in >> row;
std::cout << "column index: ";
in >> col;
}
/*
* Position Friend Func - Overloaded Binary LS Operator (outputs position to stream)
*/
std::ostream& operator<<(std::ostream &out, const Position &P) {
P.display(out);
return out;
}
/*
* Position Friend Func - Overloaded Binary RS Operator (inputs position from stream)
*/
std::istream& operator>>(std::istream &in, Position &P) {
P.input(in);
return in;
}
------------------------------------------------------------------------------------------------------------
//Position.h
#ifndef __POSITION
#define __POSITION
#include <iostream>
/*
* Direction Enumeration
*/
enum Direction {
DOWN,
LEFT,
UP,
RIGHT,
NONE
};
/*
* Next Direction - Get next direction from direction d
*/
extern Direction next_direction(Direction d);
/*
* Position class - Represents rxc grid for maze
*/
class Position {
friend std::ostream& operator<<(std::ostream &out,const Position &P);
friend std::istream& operator>>(std::istream &in, Position &P);
public:
static const std::size_t POSMAX = 22;
Position() : row(0), col(0) {};
Position(std::size_t m) : row(m), col(m) {};
Position(std::size_t r, std::size_t c) : row(r), col(c) {};
std::size_t getRow() const { return row; }
std::size_t getCol() const { return col; }
void input();
Position Neighbor(Direction d) const;
bool operator==(const Position &other) const;
bool operator!=(const Position &other) const;
void display(std::ostream &out) const;
void input(std::istream &in);
private:
std::size_t row;
std::size_t col;
};
#endif
---------------------------------------------------------------------------------
//PrintMacros.h
#ifndef PrintMacros_h
#define PrintMacros_h
/*- println - Print newline(s) / with newlines -*/
#define println(...) _println_x(, ##__VA_ARGS__ ,
_println_3(__VA_ARGS__), _println_2(__VA_ARGS__),
_println_1(__VA_ARGS__), _println_0(__VA_ARGS__)
)
/*- printx - Print var to cout / to other stream -*/
#define printx(...) _printx_x(, ##__VA_ARGS__ ,
_printx_2(__VA_ARGS__), _printx_1(__VA_ARGS__)
)
/*- println: 0-3 arguments: -*/
#define _println_x(x, s, t, u, FUNC, ...) FUNC
// 0 - Print single newline
#define _println_0() (printx(std::endl))
// 1 - Print 's' newlines
#define _println_1(s) do {
for (int i {0}; i < s; ++i)
_println_0();
} while (0)
// 2 - Print 's' newlines then 't' on current line
#define _println_2(s,t) do {
_println_1(s);
printx(t);
} while (0)
// 3 - Print 's' newlines, then 't', then 'u' newlines
#define _println_3(s,t,u) do {
_println_2(s,t);
_println_1(u);
} while (0)
/*- printx: 1-2 arguments: -*/
#define _printx_x(x, s, t, FUNC, ...) FUNC
// 1 arg - Print 's' to cout
#define _printx_1(s) (std::cout << s)
// 2 args - Print 's' to output stream 't'
#define _printx_2(s, t) (t << s)
#endif /* PrintMacros_h */
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.