有人可以帮助您获得带障碍的最短路径吗？

Question

我有一个2D矩阵。给定一个二维矩阵，其中某些元素用“ 1”填充，其余元素用“ 0”填充，除了2个元素外，其中一个是S（起点）和D（终点）。这里的“ 0”表示您无法遍历该特定点。您可以从一个单元格向左，向右，向上或向下移动。给定矩阵中的两个点，找到这些点之间的最短路径。

最短的路径之一（从S到D都互斥）是：[（3，2），（3，1），（2，1），（2，0）]。如果S和D之间没有路径，则返回null。

我写了一段代码，该代码返回从S到D的距离，我的方法返回int，但是如何返回预期的输出？我的代码：

---

public class ShortestPath {

     public static void main(String args[])
        {
            char[][] matrix = {
                {'S', '0', '1', '1'},
                {'1', '1', '0', '1'},
                {'0', '1', '1', '1'},
                {'1', '0', 'D', '1'}
            };

            int path = pathExists(matrix);

           System.out.println(path);
        }

    private static int pathExists(char[][] matrix) {

        Node source = new Node(0, 0, 0);
        Queue<Node> queue = new LinkedList<Node>();

        queue.add(source);

        while(!queue.isEmpty()) {
            Node poped = queue.poll();

            if(matrix[poped.x][poped.y] == 'D' ) {
                return poped.distanceFromSource;
            }
            else {
                matrix[poped.x][poped.y]='0';

                List<Node> neighbourList = addNeighbours(poped, matrix);
                queue.addAll(neighbourList);
            }   
        }
        return -1;
    }

    private static List<Node> addNeighbours(Node poped, char[][] matrix) {

        List<Node> list = new LinkedList<Node>();

        if((poped.x-1 > 0 && poped.x-1 < matrix.length) && matrix[poped.x-1][poped.y] != '0') {
            list.add(new Node(poped.x-1, poped.y, poped.distanceFromSource+1));
        }
        if((poped.x+1 > 0 && poped.x+1 < matrix.length) && matrix[poped.x+1][poped.y] != '0') {
            list.add(new Node(poped.x+1, poped.y, poped.distanceFromSource+1));
        }
        if((poped.y-1 > 0 && poped.y-1 < matrix.length) && matrix[poped.x][poped.y-1] != '0') {
            list.add(new Node(poped.x, poped.y-1, poped.distanceFromSource+1));
        }
        if((poped.y+1 > 0 && poped.y+1 < matrix.length) && matrix[poped.x][poped.y+1] != '0') {
            list.add(new Node(poped.x, poped.y+1, poped.distanceFromSource+1));
        }       
        return list;
    }
}
class Node {
    int x;
    int y;
    int distanceFromSource;

    Node(int x, int y, int dis) {
        this.x = x;
        this.y = y;
        this.distanceFromSource = dis;
    }
}

---

Answer 1

您本质上是在实现BFS（广度优先搜索）以检测从源（S）到目标（D）的路径的存在。您只需跟踪路径，即可在Node定义中维护父Node。