A Maze is given as N*N binary matrix of cells where source cell is the upper lef
ID: 3700801 • Letter: A
Question
A Maze is given as N*N binary matrix of cells where source cell is the upper left most cell i.e., maze[0][0] and destination cell is lower rightmost block i.e., maze[N-1][N-1]. A mouse starts from the source and tries to reach the destination by moving in one of possible four directions. The mouse can move one cell above, right, left, or below, provided that cell is safe to go. It cannot move diagonally. This maze can be represented by a 2d matrix as 1’s and 0’s, where 1 represents safe to go and 0 represents unsafe (no go). The goal is for the mouse to go to the destination from the source by only using safe cells.
Gray cells are unsafe (value = 0).
Following is the matrix representation of the above maze.
A solution to the maze problem is a mouse trail which captures all the cells that the mouse attempts to navigate through to reach the destination. It does not have to be the shortest way. For instance, one mouse trail solution for the above maze is { (0,0), (1,0),(1,1),(2,1),(3,1),(3,0),(3,2),(3,3)} and another one is { (0,0), (1,0),(1,1),(2,1),(3,1),(3,2),(3,3)}. Both are good and correct, even though the second one is shorter. Your solution should work for all mazes of size N x N where N>=4. Notice that the maze problem may not have a solution – for instance, if all of the cells of row 2 are unsafe, the mouse cannot get to the destination.
Problem 1: Your Java code will print out any one mouse trail if there is a solution, otherwise, it should print “no solution”. In this you will use iterative (non-recursive) algorithm as the basis using an explicit Stack<..> from Java.util.* package.
Source DestExplanation / Answer
public class MouseMaze
{
final int N = 4;
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] +
" ");
System.out.println();
}
}
boolean isSafe(int maze[][], int x, int y)
{
return (x >= 0 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}
boolean findMaze(int maze[][])
{
int sol[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
if (x == N - 1 && y == N - 1)
{
sol[x][y] = 1;
return true;
}
if (isSafe(maze, x, y) == true)
{
sol[x][y] = 1;
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
MouseMaze rat = new MouseMaze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.findMaze(maze);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.