Question: The following code contains a helper method boolean winnable(int maze[][], int startRow, int startCol, boolean[][] marked). This method returns true if it is possible to
The following code contains a helper method boolean winnable(int maze[][], int startRow, int startCol, boolean[][] marked).
This method returns true if it is possible to solve the maze, starting in the location maze[startRow][startCol] and ending in the bottom-right.
If the maze is winnable, modify the maze array by filling in the winning path with 2s. Otherwise, the maze should not be modified. It does not have to be the shortest path. Any path is fine. Write the missing code so it works correctly. No other method should be changed. Thank you for any assistance.
The rules of the maze:
-Each maze is represented by a 2D int array.
-You can move in 4 directions: up, down, left, or right. You cannot move diagonally.
-1 represents a wall. 0 represents empty space. You cannot move through a wall.
-The maze is winnable if there exists a sequence of moves that brings you from the starting location to the ending location.
* Do not visit invalid locations, i.e. locations that contain walls or locations outside the maze.
* If you return true, you must be on the winning path, so you can fill in the entry with 2 before returning true.
import java.util.*;
public class HW4 {
// Returns true if it is possible to solve the maze,
// starting in the top-left and ending in the bottom-right.
public static boolean winnable(int maze[][]) {
boolean marked[][] = new boolean[maze.length][maze[0].length];
return winnable(maze, 0, 0, marked);
}
// Returns true if it is possible to solve the maze,
// starting in the location maze[startRow][startCol] and ending in the bottom-right.
// If the maze is winnable, this method modifies the maze array by filling in the winning path with 2s.
// Otherwise, the maze is not modified.
public static boolean winnable(int maze[][], int startRow, int startCol, boolean[][] marked) {
int numRows = maze.length, numCols = maze[0].length;
// If you already won, return true.
// Mark the current location as visited.
// Call winnable recursively on each adjacent location that hasn't been visited yet.
// (do not visit invalid locations, i.e. locations that contain walls or locations outside the maze)
// If you can win from any adjacent location, fill in the entry with 2 and return true.
// Otherwise return false.
}
public static void print(int maze[][]) {
for (int[] row : maze)
System.out.println(Arrays.toString(row));
}
public static void main(String[] args) {
int[][] maze1 = {{0, 0, 0, 1, 1},
{1, 1, 0, 1, 1},
{0, 0, 0, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
int[][] maze2 = {{0, 0, 0, 0, 1},
{0, 1, 0, 1, 1},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 0},
{1, 0, 1, 0, 0}};
int[][] maze3 = {{0, 0, 0, 0, 1},
{0, 1, 1, 0, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},
{1, 0, 0, 0, 0}};
int[][] maze4 = {{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 1, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0}};
int[][] maze5 = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 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, 1, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 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, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
// For each maze, call the winnable method, then print the maze.
// Winnable mazes should have their winning paths filled in with 2s.
System.out.println("maze1: " + winnable(maze1)); // true
print(maze1);
System.out.println(" maze2: " + winnable(maze2)); // false
print(maze2);
System.out.println(" maze3: " + winnable(maze3)); // true
print(maze3);
System.out.println(" maze4: " + winnable(maze4)); // false
print(maze4);
System.out.println(" maze5: " + winnable(maze5)); // true
print(maze5);
}
}
Sample output:
maze1: true
[2, 2, 2, 1, 1]
[1, 1, 2, 1, 1]
[2, 2, 2, 1, 1]
[2, 1, 1, 1, 1]
[2, 2, 2, 2, 2]
maze2: false
[0, 0, 0, 0, 1]
[0, 1, 0, 1, 1]
[0, 1, 1, 0, 0]
[0, 0, 0, 1, 0]
[1, 0, 1, 0, 0]
maze3: true
[2, 0, 0, 0, 1]
[2, 1, 1, 0, 1]
[2, 1, 1, 0, 1]
[2, 2, 1, 1, 1]
[1, 2, 2, 2, 2]
maze4: false
[0, 1, 0, 0, 0]
[0, 1, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 1, 0, 1, 0]
[0, 0, 0, 1, 0]
maze5: true
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0]
[0, 0, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0]
[0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help