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 1s and 0s, 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.

{1, 0, 0, 0}

{1, 1, 0, 1}

{0, 1, 0, 0}

{1, 1, 1, 1}

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 Dest