Modify the maze in the MazeSearch.java program, such that 1. The maze cannot be
ID: 3827698 • Letter: M
Question
Modify the maze in the MazeSearch.java program, such that
1. The maze cannot be traversed.
2. There are 2 different paths to traverse the maze.
//********************************************************************
// Maze.java Author: Lewis/Loftus
//
// Represents a maze of characters. The goal is to get from the
// top left corner to the bottom right, following a path of 1s.
//********************************************************************
public class Maze
{
private final int TRIED = 3;
private final int PATH = 7;
private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };
//-----------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
//-----------------------------------------------------------------
public boolean traverse(int row, int column)
{
boolean done = false;
if (valid(row, column))
{
grid[row][column] = TRIED; // this cell has been tried
if (row == grid.length-1 && column == grid[0].length-1)
done = true; // the maze is solved
else
{
done = traverse(row+1, column); // down
if (!done)
done = traverse(row, column+1); // right
if (!done)
done = traverse(row-1, column); // up
if (!done)
done = traverse(row, column-1); // left
}
if (done) // this location is part of the final path
grid[row][column] = PATH;
}
return done;
}
//-----------------------------------------------------------------
// Determines if a specific location is valid.
//-----------------------------------------------------------------
private boolean valid(int row, int column)
{
boolean result = false;
// check if cell is in the bounds of the matrix
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[row].length)
// check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true;
return result;
}
//-----------------------------------------------------------------
// Returns the maze as a string.
//-----------------------------------------------------------------
public String toString()
{
String result = " ";
for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += " ";
}
return result;
}
}
//********************************************************************
// MazeSearch.java Author: Lewis/Loftus
//
// Demonstrates recursion.
//********************************************************************
public class MazeSearch
{
//-----------------------------------------------------------------
// Creates a new maze, prints its original form, attempts to
// solve it, and prints out its final form.
//-----------------------------------------------------------------
public static void main(String[] args)
{
Maze labyrinth = new Maze();
System.out.println(labyrinth);
if (labyrinth.traverse(0, 0))
System.out.println("The maze was successfully traversed!");
else
System.out.println("There is no possible path.");
System.out.println(labyrinth);
}
}
Explanation / Answer
-solution 1
class MazeSearch {
public static void main (String[] args) {
Maze labyrinth = new Maze();
System.out.println(labyrinth);
if (labyrinth.traverse(0, 0))
System.out.println("The maze was successfully traversed!");
else
System.out.println("There is no possible path.");
System.out.println(labyrinth);
}
}
class Maze {
private final int TRIED = 3;
private final int PATH = 7;
int[][] grid = {{1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1}};
public String toString()
{
String result = " ";
for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += " ";
}
return result;
}
public boolean traverse (int row, int column) {
boolean done = false;
if (valid (row, column)) {
grid[row][column] =TRIED ;
if (row == grid.length && column == grid[0].length)
done = true;
else {
done = traverse (row+1, column);
if (!done)
done = traverse (row, column+1);
if (!done)
done = traverse (row-1, column);
if (!done)
done = traverse (row, column-1);
}
if (done)
grid[row][column] = 7;
}
return done;
}
private boolean valid (int row, int column) {
boolean result = false;
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[0].length)
if (grid[row][column] == 1)
result = true;
return result;
}
}
/*
output:
1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111
There is no possible path.
3330330003333
3033303333003
0000303030300
3330333030333
3030000333003
3033333303333
3000000000000
3333333333333
*/
// Solution 2
public class Maze
{
private final int TRIED = 3;
private final int PATH = 7;
private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };
public boolean traverse(int row, int column)
{
boolean done = false;
if (valid (row, column)) {
grid[row][column] =TRIED ;
if (row == grid.length-1 && column == grid[0].length-1)
done = true;
else {
done = traverse (row+1, column);
if (!done)
done = traverse (row, column+1);
if (!done)
done = traverse (row-1, column);
if (!done)
done = traverse (row, column-1);
}
if (done)
grid[row][column] = 7;
}
return done;
}
private boolean valid(int row, int column)
{
boolean result = false;
// check if cell is in the bounds of the grid
if (row >= 0 && row < grid.length &&
column >= 0 && column < grid[row].length)
// check if cell is not blocked and not previously tried
if (grid[row][column] == 1)
result = true;
return result;
}
public String toString()
{
String result = " ";
for (int row=0; row < grid.length; row++)
{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += " ";
}
return result;
}
}
public class MazeSearch
{
public static void main(String[] args)
{
Maze labyrinth = new Maze();
System.out.println(labyrinth);
if (labyrinth.traverse(0, 0))
System.out.println("The maze was successfully traversed!");
else
System.out.println("There is no possible path.");
System.out.println(labyrinth);
}
}
/*
output:
1110110001111
1011101111001
0000101010100
1110111010111
1010000111001
1011111101111
1000000000000
1111111111111
The maze was successfully traversed!
7770110001111
3077707771001
0000707070300
7770777070333
7070000773003
7077777703333
7000000000000
7777777777777
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.