Write a Maze Explorer program, MazeExplorer.cpp, that uses stacks and queues to

Question

Write a Maze Explorer program, MazeExplorer.cpp, that uses stacks and queues to implement an algorithm to escape from a maze. The overall pseudocode of the algorithm is the following.

create an empty stack of locations to explore.

push the start location onto the stack.

while ( stack is not empty ) {

pop a location loc from the stack.

if we have pulled loc from the stack before:

no need to explore it again, so skip loc.

if loc is the end location:

the end was reachable!

else, loc is a new reachable non-finish location, so explore it:

add all non-wall adjacent maze locations to the stack.

record the fact that we have explored loc.

}

if the stack is empty, the finish is unreachable.

A maze is specified by a file which contains a text encoding for the maze, where S represents the start location, F represents the finish location, W represents a wall, and O represents a location we can explore. A path through the maze can only consist of steps going left, right, up, or down, no diagonals are allowed.

Two mazes are provided as input: Maze1.txt (in which the end is reachable) and Maze2.txt (inwhich, the end is not reachable).

Here is a sample maze:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW

WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW

WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW

WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW

WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW

WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW

WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW

WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW

WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW

WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Image text transcribed for accessibility: Write a Maze Explorer program, MazeExplorer.cpp, that uses stacks and queues to implement an algorithm to escape from a maze. The overall pseudocode of the algorithm is the following. create an empty stack of locations to explore.

Explanation / Answer

#include<iostream>

#include<vector>

#include<stack>

#include<queue>

#include<list>

#include<map>

#include<set>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define U unsigned long long int

#define INF 9999999

#define NIL -1

using namespace std;

char arr[1001][1001];

int level[1001][1001];

bool visited[1001][1001];

main()

{

int row,col,i,j,k,l;

scanf("%d%d",&row,&col);

// memset(arr,0,sizeof(arr));

int srow,scol,drow,dcol;

for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

cin>>arr[i][j];

if(arr[i][j]=='S')

{

srow=i;

scol=j;

}

if(arr[i][j]=='E')

{

drow=i;

dcol=j;

}

}

}

queue< pair<int,int> >myq;

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

visited[i][j]=0;

level[i][j]=999999;

//cout<<arr[i][j]<<" ";

}

//cout<<endl;

}

myq.push(make_pair(srow,scol));

visited[srow][scol]=1;

level[srow][scol]=0;

while(!myq.empty())

{

pair<int,int> pq=myq.front();

int pi=pq.first;

int pj=pq.second;

if(pi==drow && pj==dcol)

break;

myq.pop();

for(k=-1;k<=1;k++)

{

for(l=-1;l<=1;l++)

{

//cout<<"asas";

if(k!=l && l+k!=0 && pi+k>=0 && pi+k<row && pj+l>=0 && pj+l<col &&( arr[pi+k][pj+l]=='O' || arr[pi+k][pj+l]=='E') && visited[pi+k][pj+l]==0)

{

//cout<<"asas";

visited[pi+k][pj+l]=1;

myq.push(make_pair(pi+k,pj+l));

level[pi+k][pj+l]=level[pi][pj]+1;

}

}

}

}

if(level[drow][dcol]!=999999)

cout<<"shortest distance between source and destination is "<<level[drow][dcol]<<endl;

else

cout<<"destination is not reachable"<<endl;

//system("pause");

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.