我已经成功地做​​到了最短路径算法迷宫（见下文code）。不过，我想以最短路径的坐标存储到传递到我的函数的栈参数。可能有人请告诉我如何我能做到这一点？ 这里是我工作的迷宫：

I have successfully done up a shortest path algorithm for a maze (see code below). However, I want to store the coordinates of the shortest path into the Stack parameter that is passed into my function. Could someone please advise me on how I could achieve this? Here is the maze that I am working on:

注：1：长城，0：有效路径，S：开始，E：结束

Legend: 1: Wall, 0: valid path, s: start, e: end

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" },
     };

我的算法：

// Pre-condition: Two integers indicating the row and col number to start from,
// a 2d array of string objects representing the map of the maze,
// a 2d array of booleans mapping out the visited cells in the maze
// A string array containing the map of the maze.
// An empty Stack object
// Post-conditon: The distance of the shortest path from the current cell(start)
// to the end of the maze
public static int shortestPath(int row,int col,boolean[][] visited,String[][] map,Stack<Pair> path)
{
    if(row < 0 || row >= map.length || col < 0 || col >= map[0].length)
        return -1;
    else if(visited[row][col] == true)
        return -1;
    else if(map[row][col].equals("e"))
        return 0;
    else
    {
        // Mark the current cell as visited
        visited[row][col] = true;

        // There is a wall
        if(map[row][col].equals("1"))
            return -1;
        else
        {
            int[] pathDist = new int[4];

            // Start finding the path from the left
            int left  = 1 + shortestPath(row,col-1,visited,map,path);

            // Start searching from the right
            int right = 1 + shortestPath(row,col+1,visited,map,path);

            // Start searching from the bottom
            int down  = 1 + shortestPath(row+1,col,visited,map,path);

            // Start searching from the top
            int up    = 1 + shortestPath(row-1,col,visited,map,path);

            visited[row][col] = false;

            pathDist[0] = left;
            pathDist[1] = right;
            pathDist[2] = down;
            pathDist[3] = up;

            Arrays.sort(pathDist);

            for(Integer i : pathDist)
                if(i > 0) return i;
            return -1;
        }
    }
}

}

推荐答案

也有一些是根本性的错误你的方法：你计算的所有可能通过迷宫的路径，然后从中挑选最短的一个。试着改变你的输入地图

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).

这将是更好地使用某种 Dijkstra的，在其中保持从地图开始位置的距离。

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 + "}";
    }
}

主要算法，基于Dijkstra的是如下。它遵循的迷宫，那是一个面包优先遍历，它首先访问的所有单元格，在距离1从一开始，下一回合它所访问的所有单元格，在距离2从一开始，依此类推。

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() + ", ");
    }
}

和印刷

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},