Homework SourseCPP CODE The case study at the end of Chapter 7 describes a
CPP CODE:
The case study at the end of Chapter 7 describes a recursive solution to determining whether or not a maze’s exit can be reached given some start cell. In this programming assignment you will adjust the implementation in a number of ways.The files are pasted below.
The files you should complete the implementation of are MazeDr.cpp, Maze.h, and Maze.cpp. An example test file is provided, maze1.
1. Describe the initial implementation. This can go in your details document
(at least two paragraphs).
2. Allow the maximum size of the input maze to be at least 50 × 50. Describe
in your details document what you had to change to achieve this.
3. Adjust the program to allow diagonal moves. Again, describe the changes
in your details document.
4. Return the path from the start cell to the exit by visually displaying the
nodes tested and where the nodes came from. You can do this by tracking
the parent cell of each node and displaying a different character than the
ones already defined. After returning whether or not a path exists the
maze with the path should be output.
5. Adjust the driver program to allow the user to specify whether or not a new
cell is being tested in the current maze or to load a new maze. This should
make testing easier for the user.
6. Create 5 different mazes with all of the sizes containing more cells than a
25 × 25 grid. Run your program on 5 different start/exit cells for each
maze. Remember your program should not only output whether or not a
path exists but also should visually display the path. Your input and output
should be submitted to receive full credit.
7. Discussion items to be included in your document: 1) Can you think of an
algorithm that would find a path to the exit better (it does not need to be
recursive)? Describe the algorithm. 2) What happens to environments with
multiple exits? 3) Does the algorithm that you coded return good paths? 4)
How would you change your program to only allow moves up and to the
right?
8. Submit a specification details document that describes the changes to the
program you made and implementation of your program.
//MazeDr.cpp
//Maze.cpp
//Maze.h
Solution
Answer:
import java.io.*;
public class DetectedShortestPathInMaze
{
static int number_of_rows=10; static int number_of_columns=10;
static int begin_of_row=5; static int begin_of_coloumn=3;
static int end_of_row=1; static int end_of_coloumn=6;
static int taken_maze[][]={{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,1,0,1,1,0,1,1,1},
{1,0,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,0,1,1,1},
{1,0,1,1,1,1,0,1,0,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
static int shortestpath[]=new int[number_of_rows*number_of_columns];
static int length_short;
boolean visitedalready(int row, int col, int detectedpathsofar[], int detectedlengthsofar){
int x;
int goal = row*number_of_columns+col;
for (x=0;x<detectedlengthsofar;x++)
if (detectedpathsofar[x]==goal) return true;
return false;
}
public void displayupdatedpath(int takenpath[], int takenlength){
int r,c;
for (r=0;r<number_of_rows;r++){
for(c=0;c<number_of_columns;c++){
if (taken_maze[r][c]==1)
System.out.print(\"|\");
else if (r==begin_of_row && c==begin_of_coloumn)
System.out.print(\"S\");
else if (r==end_of_row && c==end_of_coloumn)
System.out.print(\"X\");
else if (visitedalready(r,c,takenpath,takenlength))
System.out.print(\"o\");
else
System.out.print(\" \");
}
System.out.println(\"\");
}
}
public void searchnewpath(int row, int col, int detectedpathsofar[], int detectedlengthsofar){
if (row<0 || col<0 || row>=number_of_rows || col>=number_of_columns)
return;
if (taken_maze[row][col]==1) return ;
if (visitedalready(row, col, detectedpathsofar, detectedlengthsofar)) return;
int takenpath[]=new int[detectedlengthsofar+1];
System.arraycopy(detectedpathsofar, 0, takenpath, 0, detectedlengthsofar);
takenpath[detectedlengthsofar++]=row*number_of_columns+col;
if (row==end_of_row && col==end_of_coloumn){
System.out.println(\"Detected path of length \"+detectedlengthsofar+\":\");
displayupdatedpath(takenpath, detectedlengthsofar);
if (detectedlengthsofar<=length_short){
length_short=detectedlengthsofar;
System.arraycopy(takenpath, 0, shortestpath, 0, detectedlengthsofar);
System.out.println(\" The new shortest path is of length \" + detectedlengthsofar);
}
System.out.println(\"\");
return;
}
searchnewpath(row-1, col, takenpath, detectedlengthsofar);
searchnewpath(row, col-1, takenpath, detectedlengthsofar);
searchnewpath(row, col+1, takenpath, detectedlengthsofar);
searchnewpath(row+1, col, takenpath, detectedlengthsofar);
}
public static void main(String[] args)
{
int r,c,x;
int detectedpathsofar[];
int detectedlengthsofar;
DetectedShortestPathInMaze obj=new DetectedShortestPathInMaze();
detectedpathsofar=new int[obj.number_of_rows*obj.number_of_columns];
for (x=0;x<obj.number_of_rows*obj.number_of_columns;x++){
obj.shortestpath[x]=-1;
detectedpathsofar[x]=-1;
}
obj.length_short=obj.number_of_rows*obj.number_of_columns+1;
detectedlengthsofar=0;
System.out.println(\"The Maze Is Shown As Below:\");
for (r=0;r<obj.number_of_rows;r++){
for (c=0;c<obj.number_of_columns;c++){
if (r==begin_of_row && c==begin_of_coloumn)
System.out.print(\"S\");
else if (r==end_of_row && c==end_of_coloumn)
System.out.print(\"x\");
else if (obj.taken_maze[r][c]==0)
System.out.print(\" \");
else System.out.print(\"|\");
}
System.out.println(\"\");
}
System.out.println(\"\");
System.out.println(\"Searching For Paths!!!!!\");
obj.searchnewpath(begin_of_row, begin_of_coloumn, detectedpathsofar, detectedlengthsofar);
System.out.println(\"\");
System.out.println(\"The shortest path was found with the following of length \"+ obj.length_short);
obj.displayupdatedpath(obj.shortestpath, obj.length_short);
}
}
