java - 打印出最短路径的所有单元格坐标

Question

我已经成功地完成了迷宫的最短路径算法(见下面的代码)。但是，我想将最短路径的坐标存储到传递到我的函数中的 Stack 参数中。有人可以告诉我如何实现这一目标吗？ 这是我正在研究的迷宫:

图例:1:墙，0:有效路径，s:开始，e:结束

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

Answer 1

您的方法存在根本性错误:您计算了所有 迷宫中的可能路径，然后选择了最短的路径。尝试将您的输入映射更改为

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

看看会发生什么(算法永远不会终止，因为可能的路径数量巨大)。

最好使用某种 Dijkstra's ，其中您保留了距起始位置的距离图。

我引入了一个方便的类Cell来处理坐标:

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 的所有单元格，依此类推。

找到路径就是从结束单元格开始，然后沿着递减的距离返回到起始单元格。

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];
}

我使用了一些实用方法来保持算法简洁:

// 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;
}

我的主要方法如下

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