Skip to content

Instantly share code, notes, and snippets.

@Rugal
Last active November 17, 2017 17:14
Show Gist options
  • Save Rugal/6e3295a5e493cb3260996b8327eed7a4 to your computer and use it in GitHub Desktop.
Save Rugal/6e3295a5e493cb3260996b8327eed7a4 to your computer and use it in GitHub Desktop.
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment