Could anyone help me with this question please? Thank you so much! Below is an i
ID: 3744021 • Letter: C
Question
Could anyone help me with this question please? Thank you so much!
Below is an image of a simple maze (the image can also be found on eLC) 10 START 15 12 8 23 9 1411 24 20 13 21 16 _ 18 -1 17 FINISH A Using the graph representation given, implement a program that can successfully navigate through the maze from the START to FINISH wither Breadth-First Search and Depth-First Search. Your program should output one or more solutions (the path taken). You should write your own search code. Do not use predefined libraries implementing search algorithms (whether from the textbook website or elsewhere) How many solutions were you able to find?Explanation / Answer
#include<iostream>
#include <list>
using namespace std;
class Maze
{
int V; // #vertices
list<int> *adj; // pointer to adjacency list
void findpaths(int , int , bool [], int [], int &);
public:
Maze(int V)
{
this->V = V;
adj = new list<int>[V];
}
void path(int u, int v)
{
adj[u].push_back(v); // path from u to v
}
void printPossiblePath(int start, int dest)
{
bool *visited = new bool[V];
int *path = new int[V];
int i_path = 0;
for (int i = 0; i < V; i++)
visited[i] = false; //none are visited
findpaths(start, dest, visited, path, i_path);
}
};
void Maze::findpaths(int start, int dest, bool visited[],
int path[], int &index)
{
path[index] = start;
index++;
visited[start] = true; // current node is visited
if (start == dest)
{
for (int i = 0; i<index; i++)
cout << path[i] << " ";
cout << endl;
}
else
{
list<int>::iterator i;
for (i = adj[start].begin(); i != adj[start].end(); ++i)
if (!visited[*i])
findpaths(*i, dest, visited, path, index);
}
index--;
visited[start] = false;
}
int main()
{
Maze g(4);// change to 24 (total number of vertices)
g.path(0, 1);g.path(0, 2);g.path(0, 4);
g.path(2, 3);g.path(2, 4);
/* Add all the paths as per question*/
int s = 0, d = 4;
cout << "Possible Paths"<< endl;
g.printPossiblePath(s, d);
return 0;
}