[Repost] Do not Copy from other posts! Fill in only the missing code for the fun
ID: 3911112 • 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 already 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;
}
// ------------------------------RescueRemy.cpp-----------------------------
#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
here is your modified maze.cpp file : ------------>>>>>>>>>>>
#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];
}
S.push(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();
if(nbr == exit){
break;
}
vnodeptr cursor = adjList[current];
while(cursor != nullptr){
Q.push(cursor->v);
pred[cursor->v] = current;
if(cursor->v == exit){
nbr = exit;
break;
}
cursor = cursor->next;
}
// Fill in the missing code
}
return pred;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.