There is something fundamentally wrong with your approach: you compute all possible paths through the maze and then pick the shortest one. Try to change your input map to
String[][] map = new String[][] {
new String[] { "s", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "e" } };
and see what happens (the algorithm will never terminate, because the number of possible paths is huge).
It would be better to use some sort of Dijkstra's, in which you keep a map of distances from the start position.
I introduced a convenience class Cell
to deal with coordinates:
public static class Cell {
public int row;
public int col;
public Cell(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "{" + row + ", " + col + "}";
}
}
The main algorithm, based on Dijkstra's is as follows. It follows a bread-first traversal of the maze, that is, first it visits all cells at distance 1 from the start, next round it visits all cells at distance 2 from the start, and so on.
Finding the path is a matter of starting at the end cell and just following the decreasing distances back towards the start cell.
public static int shortestPath(String[][] map, Cell start, Cell end,
Stack<Cell> path) {
// initialize distances array filled with infinity
int[][] distances = new int[map.length][];
for (int i = 0; i < map.length; i++) {
distances[i] = new int[map[i].length];
Arrays.fill(distances[i], Integer.MAX_VALUE);
}
// the start node should get distance 0
int distance = 0;
List<Cell> currentCells = Arrays.asList(start);
while (distances[end.row][end.col] == Integer.MAX_VALUE
&& !currentCells.isEmpty()) {
List<Cell> nextCells = new ArrayList<>();
// loop over all cells added in previous round
// set their distance
// and add their neighbors to the list for next round
for (Cell cell : currentCells) {
if (distances[cell.row][cell.col] == Integer.MAX_VALUE
&& !map[cell.row][cell.col].equals("1")) {
distances[cell.row][cell.col] = distance;
addNeighbors(cell, nextCells, map.length, map[0].length);
}
}
// prepare for next round
currentCells = nextCells;
distance++;
}
// find the path
if (distances[end.row][end.col] < Integer.MAX_VALUE) {
Cell cell = end;
path.push(end);
for (int d = distances[end.row][end.col]-1; d >= 0; d--) {
cell = getNeighbor(cell, d, distances);
path.push(cell);
}
}
return distances[end.row][end.col];
}
I used few utility methods to keep the algorithm concise:
// add all valid neighbors of a cell to the list
// where "valid" means: indices inside the maze
private static void addNeighbors(Cell cell, List<Cell> list,
int maxRow, int maxCol) {
int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : ds) {
int row = cell.row + d[0];
int col = cell.col + d[1];
if (isValid(row, col, maxRow, maxCol))
list.add(new Cell(row, col));
}
}
// find the neighbor of a cell having a certain distance from the start
private static Cell getNeighbor(Cell cell, int distance, int[][] distances) {
int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : ds) {
int row = cell.row + d[0];
int col = cell.col + d[1];
if (isValid(row, col, distances.length, distances[0].length)
&& distances[row][col] == distance)
return new Cell(row, col);
}
return null;
}
// check if coordinates are inside the maze
private static boolean isValid(int row, int col, int maxRow, int maxCol) {
return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
}
My main method is as follows
public static void main(String[] args) {
String[][] map = new String[][]
{
new String[] { "1","1","1","0","0","0","1","1","1","1" },
new String[] { "s","0","0","0","1","1","0","0","0","1" },
new String[] { "1","1","0","0","1","0","0","1","0","1" },
new String[] { "1","1","1","0","0","0","0","0","0","1" },
new String[] { "1","0","1","1","1","0","1","1","0","1" },
new String[] { "0","0","0","0","0","0","0","0","0","1" },
new String[] { "0","1","1","1","1","1","1","1","1","1" },
new String[] { "0","0","0","0","0","0","0","0","0","e" },
};
Stack<Cell> path = new Stack<>();
System.out.println(shortestPath(map, new Cell(1, 0), new Cell(7, 9), path));
while (!path.isEmpty()) {
System.out.print(path.pop() + ", ");
}
}
and prints
25
{1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 3}, {3, 4}, {3, 5}, {4, 5}, {5, 5},
{5, 4}, {5, 3}, {5, 2}, {5, 1}, {5, 0}, {6, 0}, {7, 0}, {7, 1}, {7, 2}, {7, 3},
{7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9},