Submit each java file electronically through Campus Cruiser by the due date. Sub
ID: 3810288 • Letter: S
Question
Submit each java file electronically through Campus Cruiser by the due date. Submit a printout of your source code to the instructor by the due date Write in Java Code Your task is to write a program that starts with an initial starting point and a map of a cave. It then finds as much treasure in the cave as possible by exploring all the accessible locations. Every time you encounter treasure, your program will output the path you took from the starting point to the treasure. Every time you reach a you will retrace your steps and try another of the untried paths until you back to your starting point having explored all the paths accessible to you. Once the program has explored all accessible spots on the m it stops. Details: 1. No matter where you are in the cave, you can only travel in one of the four cardinal directions, north (up), south(down east (right) and west (left) W me E 2. Because the position on the map is a location (row, you should use a compound data structure to represent this position. The data structure you will u is a two-dimensional array. 3. When you have multiple path options, it could simplify your algorithm if you alw try the available paths in exactly the same order (such as always first look to the north, then to the west, then to the south, and finally to the east). 4. The maps have paths marked by a walls marked by a 'W', treasure mark by a 'T', and your position is marked by a 'x'.Explanation / Answer
/*
* The logic for traversal is -
* we traverse grid in DFS manner, whenever we get treasure, we print the path
* we also print the grid after every move.
* The directions we visit in ordr are up, down, left, right
*/
import java.util.*;
import java.lang.*;
import java.io.*;
class Cave
{
static ArrayList<Integer> path_x = new ArrayList<Integer>();
static ArrayList<Integer> path_y = new ArrayList<Integer>();
static boolean isValidMove(char arr[][], int visited[][],int x,int y,int r,int c) {
if(x < 0 || y < 0 || x >= r || y >= c)
return false;
if(visited[x][y] == 1)
return false;
if(arr[x][y] == '.' || arr[x][y] == 'T')
return true;
return false;
}
static void printGrid(char arr[][],int r,int c) {
for(int i=0;i<r;i++) {
System.out.println("");
for(int j=0;j<c;j++)
System.out.print(arr[i][j] + " ");
}
System.out.println("");
}
static void printPath() {
int i,s = path_x.size();
for(i=0;i<s-1;i++) {
System.out.print("("+path_x.get(i)+","+path_y.get(i)+") => ");
}
System.out.print("("+path_x.get(i)+","+path_y.get(i)+")");
System.out.println("");
}
static void caveTraversal(char arr[][], int visited[][],int x,int y,int r,int c) {
// System.out.println("x= "+x+" y= "+y);
visited[x][y] = 1;
if(arr[x][y] == 'T') {
path_x.add(x); path_y.add(y);
printPath();
path_x.remove(x); path_y.remove(y);
}
// up
if(isValidMove(arr,visited,x-1,y,r,c)) {
path_x.add(x); path_y.add(y);
arr[x][y] = '.'; arr[x-1][y] = 'x';
printGrid(arr,r,c);
caveTraversal(arr,visited,x-1,y,r,c);
}
// Down
if(isValidMove(arr,visited,x+1,y,r,c)) {
path_x.add(x); path_y.add(y);
arr[x][y] = '.'; arr[x+1][y] = 'x';
printGrid(arr,r,c);
caveTraversal(arr,visited,x+1,y,r,c);
}
// Left
if(isValidMove(arr,visited,x,y-1,r,c)) {
path_x.add(x); path_y.add(y);
arr[x][y] = '.'; arr[x][y-1] = 'x';
printGrid(arr,r,c);
caveTraversal(arr,visited,x,y-1,r,c);
}
// Right
if(isValidMove(arr,visited,x,y+1,r,c)) {
path_x.add(x); path_y.add(y);
arr[x][y] = '.'; arr[x][y+1] = 'x';
printGrid(arr,r,c);
caveTraversal(arr,visited,x,y+1,r,c);
}
}
}
class CaveTest {
public static void main (String[] args) throws java.lang.Exception
{
int r,c,x=0,y=0;
String str;
System.out.println("Enter the input file name = ");
Scanner in = new Scanner(System.in);
String filename = in.next();
try{
//Create object of FileReader
FileReader inputFile = new FileReader(fileName);
//Instantiate the BufferedReader Class
BufferedReader bufferReader = new BufferedReader(inputFile);
str = bufferReader.readLine();
String inp[] = str.split(" ");
r = Integer.parseInt(inp[0]);
c = Integer.parseInt(inp[1]);
char arr[][] = new char[r][c];
int visited[][] = new int[r][c];
for(int i=0;i<r;i++) {
str = bufferReader.readLine();
for(int j=0;j<c;j++) {
arr[i][j] = str.charAt(j);
visited[i][j] = 0;
if(arr[i][j] == 'x') {
x = i;
y = j;
}
}
}
//Close the buffer reader
bufferReader.close();
Cave.caveTraversal(arr,visited,x,y,r,c);
System.out.println("Done with finding Treasure!");
}catch(Exception e){
System.out.println("Error while reading file line by line:" + e.getMessage());
}
}
}