Maze.java

package ga.rugal.ben;

import java.util.Stack;

public class Maze {

  private final Stack<Integer> current = new Stack<>();

  private Stack<Integer> minStack = new Stack<>();

  private final int[][] map;

  public Maze(int[][] map) {
    this.map = map;
  }

  public Stack<Integer> getMinStack() {
    return minStack;
  }

  public static void main(String[] args) {
    int[][] map = new int[][]{
      new int[]{1, 1, 0, 0, 1, 1, 0, 0},
      new int[]{1, 1, 0, 0, 1, 0, 0, 0},
      new int[]{0, 0, 1, 1, 0, 0, 0, 1},
      new int[]{0, 0, 1, 1, 0, 1, 1, 0},
      new int[]{1, 1, 0, 0, 1, 1, 0, 0},
      new int[]{1, 0, 0, 1, 1, 1, 0, 0},
      new int[]{0, 0, 0, 1, 0, 0, 1, 1},
      new int[]{0, 0, 1, 0, 0, 0, 1, 1}
    };
    Maze maze = new Maze(map);
    int start = 0, end = 6;
    maze.solve(start, end);
    maze.getMinStack().push(end);
    maze.getMinStack().forEach((i) -> {
      System.out.println(i);
    });
  }

  public void solve(int start, int target) {
    this.current.push(start);
    for (int i = 0; i < this.map.length; i++) {
      //Ignore if not reachable or dead loop
      if (this.map[start][i] != 1 || this.current.contains(i)) {
        continue;
      }
      //finally reached, compare with current best bet
      if (i == target && (this.minStack.isEmpty() || this.minStack.size() > this.current.size())) {
        this.minStack = (Stack<Integer>) this.current.clone();
        continue;
      }
      //otherwise continue recursion
      this.solve(i, target);
    }
    this.current.pop();
  }
}