(IN .JAVA) Getting out of the maze. Given an N-by-N maze, write a program to fin
ID: 3810846 • Letter: #
Question
(IN .JAVA) Getting out of the maze. Given an N-by-N maze, write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N).
explore(x, y)
-------------
- Mark the current cell (x, y) as "visited."
- If no wall to north and unvisited, then explore(x, y+1).
- If no wall to east and unvisited, then explore(x+1, y).
- If no wall to south and unvisited, then explore(x, y-1).
- If no wall to west and unvisited, then explore(x-1, y).
Explanation / Answer
public class ExploreMaze {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] maze = new int[10][10]; //declare the maze as a 10x10 square
//add 1 for all cells having wall and 0 for all other cells
//to define the maze
explore(maze, 1, 1);
}
public static void explore(int[][] maze, int x, int y){
maze[x][y] = -1; // -1 indicates visited
if(x==9 && y==9) return; //solution found
if(maze[x][y+1]==0)
explore(maze,x,y+1);
else if(maze[x+1][y]==0)
explore(maze,x+1,y);
else if(maze[x][y-1]==0)
explore(maze,x,y-1);
else if(maze[x-1][y]==0)
explore(maze,x-1,y);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.