Find longest path in a maze

Problem

Given a maze some of whose cells are blocked. Left top is the entry point and right bottom is the exit point. Find the longest possible path from entry to exit that does not contain any blocked cells.

For example,
Input maze

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

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

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

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

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

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

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

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

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

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

Output longest path

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

Solution

It is solved with the following recursive logic. If we are at any intermediate point along the longest path then from that cell we need to find the longest path to the exit which does not include any of the cells  till the current path. From any cell we first mark that cell as blocked. then find all the neighboring cells that are not blocked. We call the recursive function from that neighboring cell to the exit. Find the longest of the paths and return that path after prepending it with the current cell. Then unblock the current cell.

Code

import java.util.ArrayList;
import java.util.List;

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

 private static List< cell > findLongestPath(boolean[][] maze)
 {
  Cell start = new Cell(0, 0);
  Cell end = new Cell(maze.length - 1, maze[0].length - 1);
  List< cell > path = findLongestPath(maze, start, end);
  return path;
 }

 private static List< cell > findLongestPath(boolean[][] maze, Cell start,
   Cell end)
 {
  List< cell > result = null;
  int rows = maze.length;
  int cols = maze[0].length;
  if (start.row < 0 || start.col < 0)
   return null;
  if (start.row == rows || start.col == cols)
   return null;
  if (maze[start.row][start.col] == true)
   return null;
  if (start.equals(end))
  {
   List< cell > path = new ArrayList< cell >();
   path.add(start);
   return path;
  }
  maze[start.row][start.col] = true;
  Cell[] nextCells = new Cell[4];
  nextCells[0] = new Cell(start.row + 1, start.col);
  nextCells[2] = new Cell(start.row, start.col + 1);
  nextCells[1] = new Cell(start.row - 1, start.col);
  nextCells[3] = new Cell(start.row, start.col - 1);
  int maxLength = -1;
  for (Cell nextCell : nextCells)
  {
   List< cell > path = findLongestPath(maze, nextCell, end);
   if (path != null && path.size() > maxLength)
   {
    maxLength = path.size();
    path.add(0, start);
    result = path;
   }
  }
  maze[start.row][start.col] = false;
  if (result == null || result.size() == 0)
   return null;
  return result;
 }

 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;

 }
}