Generate two files of 100 by 100 mazes. Write a C++ program that opens a file re
ID: 3550241 • Letter: G
Question
Generate two files of 100 by 100 mazes. Write a C++ program that opens a file representing an encoded maze and reads it in properly so it can be analyzed. Show your Object oriented design including what structures you chose and why you chose them.
Search the maze and find the path from start to finish using both depth first algorithm and breadth first algorithm. Print out the path. Show your Object oriented design for your search and discuss your algorithm and what data structures you used. Perform complexity analsysis. Test this on mazes of size 100 by 100. Bonus: Print out the maze and its solution two-dimensionally.
Explanation / Answer
// I have used C++, and a matrix for maze.
// I use structure point (index of matrix) that is containing 0, 1 in maze 0 means can go there, 1 means restricted.
// Person can only walk on up, down, left and right.
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
using namespace std;
struct point
{
int x;
int y;
};
int compare(map <struct point, int var>a, map <struct point, int var>b)
{
return (a[point] > b[point]) ;
}
class Maze
{
vector<struct point> result;
vector <string> maze;
public:
Maze(FILE *f1 = NULL)
{
ifstream in_stream;
string line;
while(!in_stream.eof())
{
in_stream >> line;
maze.push_back(line);
}
}
~Maze()
vector<struct point> getPointNeighbour(struct point a)
{
vector<point> list;
if (a.getleft()) list.push_back(a.getleft());
if (a.getright()) list.push_back(a.getright());
if (a.getup()) list.push_back(a.getup());
if (a.getdown()) list.push_back(a.getdown());
}
struct point getleft(struct point a)
{
if(a.x - 1 >= 0)
{
struct point b;
b.x = a.x- 1;
b.y = a.y;
if(maze[b.x][b.y])
return b;
}
return NULL;
}
struct point getright(struct point a)
{
if(a.x + 1 < maze[0].size())
{
struct point b;
b.x = a.x + 1;
b.y = a.y;
if(maze[b.x][b.y])
return b;
}
return NULL;
}
struct point getup(struct point a)
{
if(a.y - 1 >= 0)
{
struct point b;
b.y = a.y- 1;
b.x = a.x;
if(maze[b.x][b.y])
return b;
}
return NULL;
}
struct point getdown(struct point a)
{
if(a.y + 1 < maze.size())
{
struct point b;
b.y = a.y + 1;
b.x = a.x;
if(maze[b.x][b.y])
return b;
}
return NULL;
}
void ResultByQueue(struct point startpoint, struct point endpoint)
{
map <struct point, int var>hasseen;
queue <struct point> q1;
q1.push(startpoint);
hasseen[startpoint] = 1;
while(!q1.empty())
{
vector<struct point > list = getPointNeighbour(q1.front());
q1.pop();
for(int j = 0 ; j < l.size() ; j++)
{
if((list[j].x == endpoint.x) && (list[j].y == endpoint.y))
{
result.push_back(endpoint);
cout << "List of (x, y) is ";
for(int i = 0 ; i < result.size() ; i++)
{
cout << "("<< result[i].x << "," << result[i].y << ")"<< " ";
}
return
}
if(hasseen[list[j]] <= 0)
{
q1.push(lis[j]);
hasseen[list[j]] = 1;
result.push_back(list[j]);
}
}
}
if(result.empty()) cout << "error, not showing any path. " << endl;
else
{
cout << "List of (x, y) is ";
for(int i = 0 ; i < result.size() ; i++)
{
cout << "("<< result[i].x << "," << result[i].y << ")"<< " ";
}
return
}
}
void ResultStack(struct point startpoint, struct point endpoint)
{
map <struct point, int var>hasseen;
stack <struct point> s1;
s1.push(startpoint);
hasseen[startpoint] = 1;
while(!s1.empty())
{
vector<struct point > list = getPointNeighbour(s1.top());
s1.pop();
for(int j = 0 ; j < l.size() ; j++)
{
if((list[j].x == endpoint.x) && (list[j].y == endpoint.y))
{
result.push_back(endpoint);
cout << "List of (x, y) is ";
for(int i = 0 ; i < result.size() ; i++)
{
cout << "("<< result[i].x << "," << result[i].y << ")"<< " ";
}
return
}
if(hasseen[list[j]] <= 0)
{
s1.push(lis[j]);
hasseen[list[j]] = 1;
result.push_back(list[j]);
}
}
}
if(result.empty()) cout << "error, not showing any path. " << endl;
else
{
cout << "List of (x, y) is ";
for(int i = 0 ; i < result.size() ; i++)
{
cout << "("<< result[i].x << "," << result[i].y << ")"<< " ";
}
return
}
}
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.