Find shortest path in a maze

Problem

Given a maze some of whose the cells are blocked. The left top cell is the entry point and right bottom cell is the exit point. Find the shortest path, if possible, from entry to exit through non blocked cells.
For example
Given maze

_|_|_|_|_|#|_|_|_|_|

_|_|#|_|#|_|_|_|#|#|

_|#|_|_|_|#|#|#|_|#|

_|#|_|_|_|#|_|_|#|_|

#|_|#|#|_|_|_|_|_|_|

#|_|_|_|_|_|_|#|_|_|

#|_|_|#|_|_|_|_|_|_|

#|_|_|_|_|_|_|_|#|_|

_|_|_|#|_|#|#|_|_|#|

#|#|#|#|_|#|_|_|_|_|

Shortest path

(0,1),(0,2),(0,3),(1,3),(2,3),(2,4),(3,4),(4,4),(4,5),(4,6),(5,6),(6,6),(6,7),(7,7),(8,7),(8,8),(9,8),(9,9)

Solution

For shortest path we do the breadth first traversal. We mark the entry point as 1, then all the accessible cells from 1 is marked as 2, then all the accessible cells from 2 that are not already marked are marked as 3. In this way any cell that is accessible from n marked node and not already marked are marked as n+1. In this way when the exit cell is marked. We find the shortest path.

Now to reconstruct the path we start from exit. Note its mark n and any adjacent cell that has marked with  n-1 is the previous cell. Now we add previous cell in the path and search for n-2 in its adjacent cells. In this way when we reach the entry cell our path is constructed

Code

import java.util.LinkedList;
import java.util.List;

public class ShortestPathInMaze
{
 public static void main(String[] args)
 {
  boolean[][] maze = new boolean[10][10];
  makeRandomMaze(maze);
  printMaze(maze);
  List path = findShortestPath(maze);
  if (path == null)
  {
   System.out.println("No path possible");
   return;
  }
  for (Cell cell : path)
   System.out.print(cell + ",");
 }

 private static List findShortestPath(boolean[][] maze)
 {
  int[][] levelMatrix = new int[maze.length][maze[0].length];
  for (int i = 0; i < maze.length; ++i)
   for (int j = 0; j < maze[0].length; ++j)
   {
    levelMatrix[i][j] = maze[i][j] == true ? -1 : 0;
   }
  LinkedList < cell > queue = new LinkedList < cell >();
  Cell start = new Cell(0, 0);
  Cell end = new Cell(maze.length - 1, maze[0].length - 1);
  queue.add(start);
  levelMatrix[start.row][start.col] = 1;
  while (!queue.isEmpty())
  {
   Cell cell = queue.poll();
   if (cell == end)
    break;
   int level = levelMatrix[cell.row][cell.col];
   Cell[] nextCells = new Cell[4];
   nextCells[3] = new Cell(cell.row, cell.col - 1);
   nextCells[2] = new Cell(cell.row - 1, cell.col);
   nextCells[1] = new Cell(cell.row, cell.col + 1);
   nextCells[0] = new Cell(cell.row + 1, cell.col);

   for (Cell nextCell : nextCells)
   {
    if (nextCell.row < 0 || nextCell.col < 0)
     continue;
    if (nextCell.row == maze.length
      || nextCell.col == maze[0].length)
     continue;
    if (levelMatrix[nextCell.row][nextCell.col] == 0)
    {
     queue.add(nextCell);
     levelMatrix[nextCell.row][nextCell.col] = level + 1;
    }
   }
  }
  if (levelMatrix[end.row][end.col] == 0)
   return null;
  LinkedList < cell > path = new LinkedList < cell >();
  Cell cell = end;
  while (!cell.equals(start))
  {
   path.push(cell);
   int level = levelMatrix[cell.row][cell.col];
   Cell[] nextCells = new Cell[4];
   nextCells[0] = new Cell(cell.row + 1, cell.col);
   nextCells[1] = new Cell(cell.row, cell.col + 1);
   nextCells[2] = new Cell(cell.row - 1, cell.col);
   nextCells[3] = new Cell(cell.row, cell.col - 1);
   for (Cell nextCell : nextCells)
   {
    if (nextCell.row < 0 || nextCell.col < 0)
     continue;
    if (nextCell.row == maze.length
      || nextCell.col == maze[0].length)
     continue;
    if (levelMatrix[nextCell.row][nextCell.col] == level - 1)
    {
     cell = nextCell;
     break;
    }
   }
  }
  return path;
 }

 private static class Cell
 {
  public int row;
  public int col;

  public Cell(int row, int column)
  {
   this.row = row;
   this.col = column;
  }

  @Override
  public boolean equals(Object obj)
  {
   if (this == obj)
    return true;
   if ((obj == null) || (obj.getClass() != this.getClass()))
    return false;
   Cell cell = (Cell) obj;
   if (row == cell.row && col == cell.col)
    return true;
   return false;
  }

  @Override
  public String toString()
  {
   return "(" + row + "," + col + ")";
  }
 }

 private static void printMaze(boolean[][] maze)
 {
  for (int i = 0; i < maze.length; ++i)
  {
   for (int j = 0; j < maze[i].length; ++j)
   {
    if (maze[i][j])
     System.out.print("#|");
    else
     System.out.print("_|");
   }
   System.out.println();
  }
 }

 private static void makeRandomMaze(boolean[][] maze)
 {
  for (int i = 0; i < maze.length; ++i)
  {
   for (int j = 0; j < maze[0].length; ++j)
   {
    maze[i][j] = (int) (Math.random() * 3) == 1;
   }
  }
  maze[0][0] = false;
  maze[maze.length - 1][maze[0].length - 1] = false;

 }
}