Use this 2 dimensional array to represent a maze: static char maze[][] = { { \'#

Question

Use this 2 dimensional array to represent a maze:
static char maze[][] =
{ { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
{ '#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#' },
{ '.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#' },
{ '#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.' },
{ '#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#' },
{ '#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#' },
{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };
The #'s represent the walls of the maze, and the dots represent locations in the possible paths through the maze. A move can be made only to a location in the array that contains a dot.

Write a recursive method to walk through the maze. The method should receive as arguments a 12-by-12 character array representing the maze and the current location in the maze. The first time the method is called, the current location should be the entry point of the maze. As the method attempts to locate the exit, it should place the character 'x' in each square in its path.

There's a simple algorithm for walking through a maze that guarantees finding an exit (if there is one). If there is no exit, you will arrive at the starting location again.

The algorithm is as follows: From the current location in the maze, try to move one space in any possible direction (down, right, up, or left). If it's possible to move in at least one direction, call the method recursively, passing the new spot on the maze as the current spot. If it's not possible to go in any direction, back up to the previous location in the maze and try a new direction from that location. This is an example of recursive backtracking.

Program the method to display the maze after each move so the user can watch as the maze is solved. The final output of the maze should display only the path needed to solve the maze. If going in a particular direction results in a dead end, the x's going in that direction should not be displayed. To display only the final path, you could mark off spots that result in a dead end with another character (perhaps '0') - or you could just let the original dots be there. Just don't leave x's in dead end paths.

The user should be shown the maze each step of the way, showing the next step of progress and asking if they want to continue (y or n). When you hit a dead end, you do not have to back out step by step, but simply move back to the place the wrong move was made and continue from there. Remember that the dead end path should not contain x's

Explanation / Answer

public class Maze
{
private char[][] maze;
private int dim;
private final char PATH = 'P';
private int total = 0;

/**
* Default constructor which initializes the character array to a (d,d) grid
* representing the maze
* @param d the dimensions
*/
public Maze(int d)
{
dim = d;
maze = new char[d][d];
}

/**
* Sets the row count of the grid representing the maze
* @param r the number of rows
*/
public void setDimension(int d)
{
this.maze = new char[d][d];
}

/**
* Gets the row count of the grid representing the maze
* @return the number of rows
*/
public int getDimension()
{
return dim;
}

/**
* Fills the maze with the explicitly supplied character array
* @param m the character array representing the maze
*/
public void fillMaze(char[][] m)
{
for(int row = 0; row < maze.length; row++)
for(int col = 0; col < maze[row].length; col++)
maze[row][col] = m[row][col];
}

/**
* Recursively navigate the maze while marking attempts with T, path with P
* @param r the row to move to
* @param c the column to move to
*/
public void navigate(int r, int c)
{
//Base Case 1: End of Maze
if(maze[r][c] == 'E')
{
total++;
maze[r][c] = PATH;
System.out.println(maze);
return;
}

//Base Case 2: Attempted move is outside of grid
if(r < 0 || r > dim - 1 || c < 0 || c > dim - 1){return;}
//Base Case 3: Attempted move is a wall of the maze
if(maze[r][c] == '1'){return;}

//Base Case 4: Attempted move is a previously used move
if(maze[r][c] == PATH){return;}

//Recursive Case
if(maze[r][c] == 'B')
maze[r][c] = PATH; //Mark the cell as part of the path for beginning

maze[r][c] = PATH; //Mark cell as part of the path

navigate(r + 1, c); //Move right
// System.out.println("I have backtracked from point (" + (r + 1) + ", " + c + ") to point (" + r + ", " + c + ")");

navigate(r, c + 1); // Move down
// System.out.println("I have backtracked from point (" + r + ", " + (c + 1) + ") to point (" + r + ", " + c + ")");

navigate(r - 1, c); //Move left
// System.out.println("I have backtracked from point (" + (r - 1) + ", " + c + ") to point (" + r + ", " + c + ")");

navigate(r, c - 1); //Move up
// System.out.println("I have backtracked from point (" + r + ", " + (c - 1) + ") to point (" + r + ", " + c + ")");

maze[r][c] = '0'; //backtracking
return;

}

/**
* Creates and returns a string representation of the grid which represents
* the maze.
* @return the string representation of the maze
*/
@Override
public String toString()
{
String result = "Solution #" + total + " ";
for(int row = 0; row < dim; row++)
{
for(int col = 0; col < dim; col++)
{
result += maze[row][col] + " ";
}
result += " ";
}
return result;
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.