Objective This project provides experience implementing an array based queue and
ID: 3805319 • Letter: O
Question
Objective This project provides experience implementing an array based queue and a linked list sequence. You will also review how to construct and use Java classes as well as obtain experience with software design and testing. ABET Program Learning Outcomes The ability to recognize the need for data structures and choose the appropriate data structure (b,c,i,j) The ability to evaluate the performance of an algorithm (b,c,i) The ability to implement and use stacks and queues (a,b,c,i,j) The ability to implement and use linked list and array based structures (a,b,c,ij) The Problem The programming problem in this project is to find a path from the entry cell (upper left corner to the exit cell (ower right corner) of a rectangular maze (labyrinth). The maze is a grid of cells. Each cell is bordered by 4 walls. Some of these walls are passable to the neighboring cell. The border line of the whole maze that is, the perimeter of the rectangle is not passable. You may consider the external walls of the entry as passable one-way in and the external walls of the exit are passable one-way out, though these assumptions are irrelevant to the solution of the programming problem. The program obtains input to build the a maze; input supplied by an external file finds a path through a maze if such a path exists displays the solution (or one of the solutions), that is a path traversing the maze; the display shows all the locations of the cells along the path on the console; the cells listed from entry to exit determines the farthest cell on an attempted path in the case the traversal failed and displays the path leading to the max distance cell creates a graphical representation of the solution (optional for bonus points) There are figures given in an attached file Figures.doc that illustrate the requirements specified in Problem description. theExplanation / 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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.