Objectives of this Assignment: This lab has the goal of teaching you how to: Rea
ID: 3822608 • Letter: O
Question
Objectives of this Assignment:
This lab has the goal of teaching you how to:
Read data into a two dimensional array
Use recursion to implement a depth first search.
implement an interface given to you, and
find your way recursively!
Description:
Recursion is handy for solving problems involving choosing one of several alternatives at each step. For this assignment, you will use recursion to solve mazes!
Each maze will be specified by a text file containing 2 integers that specify number of rows and number of columns on the first line, then # marks for barriers, one S for the starting position, and one G for the goal position. As the maze is solved, your code will leave breadcrumbs, indicated by .characters. Here is an example maze.
After finding a solution path, the result might look like this.
The sequence of moves, with U, R, D, and L indicating Up, Right, Down, and Left moves, and G indicating the Goal is reached, is
Notice that this is not the shortest path to the goal. The search method we will be implementing is a "depth-first search", and is not likely to find the shortest path.
Code Requirements:
For this assignment, you will code a single class called Maze that implements the IMaze interface.
The main method of Maze will get the filename from the command line, call the methods described in the interface to solve the maze, and print the resulting map and the solution path.
Remember, we will not call your main method, instead we will call the methods directly
Recursive Algorithm:
The findPath method described in the interface will call a private helper method called recPath. The signature of recPath is:
recPath must implement a recursive algorithm for finding a path to the goal from the position (row,col) given as an argument.
Base cases:
1. If position (row,col) is outside of the maze, return "".
2. If the character at position (row,col) in the map is a '#' or '.', return "".
3. If the character at position (row,col) in the map is a 'G', return "G". You found the goal!!
Recursive cases:
4. Mark the map at position (row,col) with a '.'
5. Try to find a path to the goal from position (row-1,col). If found, add 'U' to the returned path and return it.
6. Try to find a path to the goal from position (row,col+1). If found, add 'R' to the returned path and return it.
7. Try to find a path to the goal from position (row+1,col). If found, add 'D' to the returned path and return it.
8. Try to find a path to the goal from position (row,col-1). If found, add 'L' to the returned path and return it.
9. If you reach here, no path to the goal from (row,col) was found. Remove the mark '.' at map position (row,col), by replacing with a blank, and return "".
Examples:
To solve the above maze, make a file with the following contents.
Say it is saved in a file named maze1. The result of compiling and running your Maze class must be exactly as shown below.
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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.