Main.java

package com.panda;



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

public class Main {

  static class Point {
    int r;
    int c;

    public Point(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }

  public static List<Point> solveMaze(int[][] maze, int r0, int c0, int r, int c) {
    int rows = maze.length;
    int cols = maze[0].length; // Assumes >= 1 row
    boolean[][] visited = new boolean[rows][cols];
    List<Point> soln = solveMaze(maze, rows, cols, r0 - 1, c0 - 1, r - 1, c - 1, visited);
    LinkedList<Point> finalSoln = new LinkedList();
    for (Point p : soln) {
      finalSoln.add(new Point(p.r + 1, p.c + 1));
    }
    return finalSoln;
  }

  public static LinkedList<Point> solveMaze(
      int[][] maze, int rows, int cols, int x0, int y0, int x, int y, boolean[][] visited) {
    if (x0 == x && y0 == y) {
      LinkedList list = new LinkedList<>();
      list.add(new Point(x, y));
      return list;
    }

    // Try to go left
    int xL = x0, yL = y0 - 1;
    if (y0 > 0 && (maze[x0][y0] & 1) != 0 && !visited[xL][yL]) {
      visited[xL][yL] = true;
      LinkedList<Point> solution = solveMaze(maze, rows, cols, xL, yL, x, y, visited);
      if (solution != null) {
        solution.addFirst(new Point(x0, y0));
        return solution;
      }
    }

    // Try to go up
    int xT = x0 - 1, yT = y0;
    if (x0 > 0 && (maze[x0][y0] & 4) != 0 && !visited[xT][yT]) {
      visited[xT][yT] = true;
      LinkedList<Point> solution = solveMaze(maze, rows, cols, xT, yT, x, y, visited);
      if (solution != null) {
        solution.addFirst(new Point(x0, y0));
        return solution;
      }
    }

    // Try to go right
    int xR = x0, yR = y0 + 1;
    if (yR < cols && (maze[x0][y0] & 2) != 0 && !visited[xR][yR]) {
      visited[xR][yR] = true;
      LinkedList<Point> solution = solveMaze(maze, rows, cols, xR, yR, x, y, visited);
      if (solution != null) {
        solution.addFirst(new Point(x0, y0));
        return solution;
      }
    }

    // Try to go down
    int xB = x0 + 1, yB = y0;
    if (xB < rows && (maze[x0][y0] & 8) != 0 && !visited[xB][yB]) {
      visited[xB][yB] = true;
      LinkedList<Point> solution = solveMaze(maze, rows, cols, xB, yB, x, y, visited);
      if (solution != null) {
        solution.addFirst(new Point(x0, y0));
        return solution;
      }
    }

    return null;
  }

  // The binary integer is (B3, B2, B1, B0) = below, top, right, left
  private static int makeCell(int left, int top, int right, int bottom) {
    return left + (right << 1) + (top << 2) + (bottom << 3); // bit shifting
  }

  public static void main(String[] args) {
    check("Sanity check makecell 1,1 from the question", makeCell(0, 0, 1 ,1) == 10);

    // write your code here
    List<Point> soln = solveMaze(new int[][] {
        new int[] { makeCell(0, 0, 1, 1), makeCell(1, 0, 1, 0), makeCell(1, 1, 0, 0)},
        new int[] { makeCell(0, 1, 0, 1), makeCell(0, 0, 1, 0), makeCell(1, 0, 0, 1)},
        new int[] { makeCell(0, 1, 1, 0), makeCell(1, 0, 1, 0), makeCell(1, 1, 0, 1)},
        new int[] { makeCell(1, 0, 1, 1), makeCell(1, 0, 0, 0), makeCell(0, 1, 0, 1)},
        new int[] { makeCell(0, 1, 1, 0), makeCell(1, 0, 1, 0), makeCell(1, 1, 0, 0)},
    }, 1, 3, 4, 1);

    if (soln != null) {
      for (Point p : soln) {
        System.out.println(p.r + ", " + p.c);
      }
    }
  }

  private static void check(String test, boolean success) {
    System.out.println(success + "\t" + test);
  }

}

Output

true	Sanity check makecell 1,1 from the question
1, 3
1, 2
1, 1
2, 1
3, 1
3, 2
3, 3
4, 3
5, 3
5, 2
5, 1
4, 1

Process finished with exit code 0