Homework SourseUsing Netbeans Q1 Suppose we need to determine whether or no
Using Netbeans
Q1 .Suppose we need to determine whether or not a particular maze can be solved. We will think of the maze as composed of tall thick green hedges surrounding numerous paths. There will be a single entrance to the maze and a place where we want to get: the goal. On the computer, a maze will be a two-dimensional array of characters such:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
H H H H H H
H HHHHHHH HHHHH H H HHHHHHHHHH H HHHHH HHH HHHH
H H H H H H H H H H H H H H H
H H HHHHH HHH H H HHH HHHHH H H H HHHHH HHH HHH
E H H H H GH H H H H H H
HHH HHHHHHH HHHHHHH H H H H H HHHHHHH H HHH HH HH
H H H H H H H H H H H H
H HHH HHHHH HHHHHHHHH H HH H H H HHHHH HH HHH H
H H H H H H H H H H H H
HHH H H HHH H H HHH HHH HHH HHH H HHHHHHH H H
H H H H H H H H H H H H H H HH
H H H H H H H H H H H H H H
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
Where each \'H\' represents the hedge, the \'E\' represent the entrance to the maze, the \'G\' represents the goal position and the blanks represent the paths between hedges. We will assume that the maze is stored in file called maze.
Write a Java programe to:
1. Read in the maze.
2. Mark all location tried with a dot \".\" and print the new maze to a file call maze.out.
3. Print message to say whether there is a path to the goal or not.
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);
}
}
