In this lab, you will implement a stack and queue, and. using these data structu
ID: 3865025 • Letter: I
Question
In this lab, you will implement a stack and queue, and. using these data structures, you will generate a random maze and then solve the maze. The methodology behind this process is that a stack mimics depth-first-search mechanisms while a queue mimics breadth-first-search mechanisms. In the context of a maze, you can consider depth-first-search as traversing a path through the maze until you reach a dead-end (or the exit), and then backing up until you have a new path choice, and traversing that until you reach a dead-end (or the exit), and then backing up and etc. While breadth-first-search traversal of a maze will step through all path at the same time until they reach the maze exit. Below is a sample maze solution using depth-first-search, where indicates a cell on the path and * indicates a cell visited but not on the path. Note that the routine blacked-out of the dead-end twice in the upper right-hand quadrant before eventually following the correct downward path towards the exit.Explanation / Answer
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);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.