これがあなたが始めるべきである似たようなものです。ただし、以下に示すソリューションは、右下隅に到達しようとします。その状態を緩和して、一番下の行を見つけることができます。また、この行を表す一意の値を持つように、エンコーディングを少し変更する必要があります。
public class MazeSolver {
final static int TRIED = 2;
final static int PATH = 3;
// @formatter:off
private static int[][] GRID = {
{ 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 },
{ 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
// @formatter:off
public static void main(String[] args) {
MazeSolver maze = new MazeSolver(GRID);
boolean solved = maze.solve();
System.out.println("Solved: " + solved);
System.out.println(maze.toString());
}
private int[][] grid;
private int height;
private int width;
private int[][] map;
public MazeSolver(int[][] grid) {
this.grid = grid;
this.height = grid.length;
this.width = grid[0].length;
this.map = new int[height][width];
}
public boolean solve() {
return traverse(0,0);
}
private boolean traverse(int i, int j) {
if (!isValid(i,j)) {
return false;
}
if ( isEnd(i, j) ) {
map[i][j] = PATH;
return true;
} else {
map[i][j] = TRIED;
}
// North
if (traverse(i - 1, j)) {
map[i-1][j] = PATH;
return true;
}
// East
if (traverse(i, j + 1)) {
map[i][j + 1] = PATH;
return true;
}
// South
if (traverse(i + 1, j)) {
map[i + 1][j] = PATH;
return true;
}
// West
if (traverse(i, j - 1)) {
map[i][j - 1] = PATH;
return true;
}
return false;
}
private boolean isEnd(int i, int j) {
return i == height - 1 && j == width - 1;
}
private boolean isValid(int i, int j) {
if (inRange(i, j) && isOpen(i, j) && !isTried(i, j)) {
return true;
}
return false;
}
private boolean isOpen(int i, int j) {
return grid[i][j] == 1;
}
private boolean isTried(int i, int j) {
return map[i][j] == TRIED;
}
private boolean inRange(int i, int j) {
return inHeight(i) && inWidth(j);
}
private boolean inHeight(int i) {
return i >= 0 && i < height;
}
private boolean inWidth(int j) {
return j >= 0 && j < width;
}
public String toString() {
String s = "";
for (int[] row : map) {
s += Arrays.toString(row) + "\n";
}
return s;
}
}