Question

PLEASE ANSWER IN C++!

Given the starting point in a maze, you are to find and mark a path out of the maze, which is represented by a 20x20 array of 1s (representing hedges) and 0s (representing the foot-paths). There is only one exit from the maze (represented by E). You may move vertically or horizontally in any direction that contains a 0; you may not move into a square with a 1. If you move into the square with an E, you have exited the maze. If you are in a square with 1s on three sides, you must go back the way you came and try another path. You may not move diagonally. For this program, use can ONLY use a single linked list.

Program Requirements: Your program should use single linked list ONLY for finding the path. Input of program: Input is the following array of characters (1s, 0s, and E) from an ASCII text data file (maze.txt); as follows:

E0001110000000100100

11100011101110001111

11111000101000111000

00001110101100010010

01011000101111000110

00001110000110011110

11011100110110111000

00011110110111111101

01011011110110100001

01000000000110110111

11011011010010000000

01010010011000101011

01111000101110101110

00001110000111011001

01101011101101000011

11000110100111011010

01110000100100110011

11010111110110000000

01110100011000111110

00011001000011100010

Each data line consists of one row of maze. Starting points (i.e. a row, column pair) in the maze will be input from the keyboard.

Output of program: Echo print the maze complete with numbered rows and columns prior to asking the user for their starting point. For each entry into the maze, print the complete maze with a S in the starting point followed by the words ‘I am free’ if you have found a path out of the maze or the words ‘Help, I am trapped’ if you cannot. Your output could be in two formats: Print the path (by using a series of pluses (+)) you took through the maze should one be found OR Print the path as a single linked list. A program heading in the following format should begin your program:

// Program Name

// <your name>

// <date>

Answer 1

The C++ code of the above question is given as follows in which we have used dfs and visited arr of Boolean type to maintain the visited path to eliminate the stack over flow and repeatitive calls :

As per the question the input and output formats were not properly described and were written in confusion, so as far as I get the question and done it. Besides the main logic still remains the same.

//C++ code

#include <iostream>
using namespace std;

bool dfs(string arr[],bool visited[20][20],int i,int j){
  
if(i<0 || j<0 || i>=20 || j>=20 || visited[i][j]==1 || arr[i][j]=='1'){
return 0;
}
  
if(arr[i][j]=='E'){
return 1;
}
  
visited[i][j]=1;
  
bool s = dfs(arr,visited,i+1,j)
|| dfs(arr,visited,i-1,j)
|| dfs(arr,visited,i,j-1)
|| dfs(arr,visited,i,j+1);
  
if(!s){

visited[i][j] = 0;
}
  
return s;
  
}

int main() {
   string arr[20]={"E0001110000000100100",
"11100011101110001111",
"11111000101000111000",
"00001110101100010010",
"01011000101111000110",
"00001110000110011110",
"11011100110110111000",
"00011110110111111101",
"01011011110110100001",
"01000000000110110111",
"11011011010010000000",
"01010010011000101011",
"01111000101110101110",
"00001110000111011001",
"01101011101101000011",
"11000110100111011010",
"01110000100100110011",
"11010111110110000000",
"01110100011000111110",
"00011001000011100010"};

bool visited[20][20];
  
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
visited[i][j]=0;
}
}
  
int si;
int sj;
  
cin>>si;
cin>>sj;
  
bool ans = dfs(arr,visited,si-1,sj-1);
  
if(ans==1){
cout<<si<<" "<<sj<<endl;
cout<<"I am free."<<endl;
}else{
cout<<"I am trapped"<<endl;
}
  
if(ans){
  
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(visited[i][j]==1){
cout<<"+";
}
else{
cout<<arr[i][j];
}
}
cout<<endl;
}
}
  
   return 0;
}

For the input of
si=2

sj=6

the output is:

2 6
I am free.
E+++1110000000100100
111+++11101110001111
11111000101000111000
00001110101100010010
01011000101111000110
00001110000110011110
11011100110110111000
00011110110111111101
01011011110110100001
01000000000110110111
11011011010010000000
01010010011000101011
01111000101110101110
00001110000111011001
01101011101101000011
11000110100111011010
01110000100100110011
11010111110110000000
01110100011000111110
00011001000011100010