# Write a recursive method that finds a path in a given maze. A maze consists of
ID: 3626734 • Letter: #
Question
# Write a recursive method that finds a path in a given maze. A maze consists of open spaces (represented by 1s) and walls (repesented by 0s). So, we can represent a maze with a 2-dimensional array of 0s and 1s. The goal is to get from the top left corner to the bottom right, following a path of 1's.You will implement methods in Maze.java to solve such a maze using recursion. You will be given a maze and will return the solved maze (using 2s to mark the path) or null if there is no solution.
For example, the following maze:
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
0 1 0 0 1
1 1 1 0 1
Has the following solution:
2 1 1 1 1
2 0 0 0 0
2 2 2 2 2
0 1 0 0 2
1 1 1 0 2
Hints:
# Use the construction of the maze (i.e. rectangular, constant starting and ending points, etc) to your advantage.
# You are allowed to modify the contents of the maze if that aids in a solution - the only requirement is that you return a properly solved maze. It might be helpful to keep track of which spaces you've already visited.
# Under what conditions is there a path from a given open space to the bottom-right space?
Explanation / Answer
please rate - thanks
works on any 5 x 5 maze
public class MazeTest {
public static void main(String[] args) throws Exception{
Maze m = new Maze(5,5,0);
m.fillMaze();
System.out.println("Maze");
m.printMaze();
m.traverseMaze(0,0);
System.out.println(" Traversed");
m.printMaze();
}
}
----------------------------------------
import java.util.*;
import java.io.*;
public class Maze
{
private int maze[][];
private int rows;
private int cols;
private int wall ;
private boolean done;
public Maze(int r, int c, int w)
{
rows = r;
cols = c;
wall = w;
done=false;
maze = new int[rows][cols];
}
public void fillMaze()throws FileNotFoundException
{Scanner in=new Scanner(System.in);
System.out.println("Enter the name of the file");
Scanner input = new Scanner(new FileReader(in.next()));
int i;
int j;
for(i=0;i<rows;i++)
for(j=0;j<cols;j++)
maze[i][j]=input.nextInt();
}
public void printMaze()
{int i;
int j;
for(i=0;i<rows;i++)
{for(j=0;j<cols;j++)
System.out.print(maze[i][j]+" ");
System.out.println();
}
}
public Boolean traverseMaze(int row,int column)
{if(done)
return true;
if( row>=rows||column>=cols||row<0||column<0||
maze[row][column] ==2|| maze[row][column]== wall )
return false;
maze[row][column]=2;
if(row==rows-1&&column==cols-1)
{maze[row][column]=2;
for(int i=0;i<rows;i++)
for(int j=0;j<cols;j++)
if(maze[i][j]==3)
maze[i][j]=1;
done=true;
return true;
}
else
{traverseMaze(row+1,column);
if(!done)
traverseMaze(row,column-1);
if(!done)
traverseMaze(row-1,column);
if(!done)
traverseMaze(row,column+1);
}
if(!done)
maze[row][column]=3;
return true;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.