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.

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.

Problem 2: 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 a recursive algorithm as the basis. Notice that the above website has a solution to the recursive version albeit it does not work for the general case we have here. You are welcome to get some ideas from the website or simply modify the code from Problem 1 to solve it recursively.