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

Question

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

最短路径之一（从 S 到 D 均不包括）是：[(3, 2), (3, 1), (2, 1), (2, 0)]。 Return 如果 S 和 D 之间没有路径，则为 null。

我写了一段代码，其中 returns 从 S 到 D 的距离，我的方法 returns int 但是如何 return 作为预期的输出？我的代码：

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) 的路径是否存在。跟踪路径所需要做的就是在节点定义中维护一个父节点。

将起始节点的父节点设置为空。然后，当您从 current 节点发现 BFS 中的节点时，将发现节点的 parent 设置为 current节点.

现在，如果您的搜索成功（即您在搜索中点击了 D），只需从 D 向后遍历父节点链，直到您点击 S，将访问过的父节点放入堆栈中。

最后继续弹出堆栈直到它变空以获得从 S 到 D 路径上的节点。

Answer 2

你只得到距离，因为你只返回源和目的地之间的距离。按照这些来求解并打印路线；

算法 1:-

    just print the node value when you are updating the distance calculation.

算法 2:-

     1. create a queue to store the nodes. 
     2. insert the  node point of S to queue
     3. keep adding to the node value to queue when you are adding the value to distance. unless reaching to 'D'
     4. now just print the nodes from the queue which will print the path structure.

Answer 3

class Cello {
    int row;
    int col;
    public Cello(int rowIndex, int colIndex) {
        super();
        this.row = rowIndex;
        this.col = colIndex;
    }   

     @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Cello cell = (Cello) o;
            return row == cell.row &&
                    col == cell.col;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col);
        }
}   



public class ShortestPathWithParentChildMap {

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


        List<int[]> path = shortestPath(grid2);

         System.out.println("Path length:" + (path.size() - 1));
            path.stream().forEach(i -> {
                System.out.println("{" + i[0] + "," + i[1] + "}");
            });
    }

    private static void bfs(char[][] grid, Cello start, List<int[]> path) {

         int[] xDirs = new int[] {0,0,1, -1};
          int[] yDirs = new int[] {1,-1, 0, 0};

            Queue<Cello> bfsQueue = new LinkedList<>();
            bfsQueue.add(start);
            HashMap<Cello, Cello> parentMap = new HashMap<>();
            boolean[][] visited = new boolean[grid.length][grid[0].length];
            Cello endCell = null;
            while(!bfsQueue.isEmpty()) {
                boolean flag = false;
                Cello from = bfsQueue.poll();

                for (int k = 0; k < xDirs.length; ++k) {
                    int nextX = from.row + xDirs[k];
                    int nextY = from.col + yDirs[k];

                    if (nextX < 0 || nextX >= grid.length || nextY < 0 
                            || nextY >= grid[0].length || grid[nextX][nextY] == '0' 
                            || visited[nextX][nextY]) {
                        continue;
                    }

                    visited[nextX][nextY] = true;
                    Cello nextCell = new Cello(nextX, nextY);
                    bfsQueue.add(nextCell);
                    //we need a way to determine from where we have reached here
                    //storing the child to parent mapping, this will be used to retrieve the entire path
                    parentMap.put(nextCell, from);
                    //if (grid[nextX][nextY] == 'E') 
                    if (grid[nextX][nextY] == 'D') {
                        endCell = new Cello(nextX, nextY);
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
            Stack<Cello> stack = new Stack<>();
            stack.push(endCell);

            //build the path from destination to source
            while (true) {
                Cello fromCell = parentMap.get(endCell);
                stack.push(fromCell);
                if (fromCell == start) break;
                endCell = fromCell;
            }
           //reverse the above path and convert as List<int[]>
            while (!stack.isEmpty()) {
                Cello p = stack.pop();
                path.add(new int[] {p.row, p.col});
            }
    }

    private static List<int[]> shortestPath(char[][] grid) {
        ArrayList<int[]> path = new ArrayList<>();
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (grid[i][j] == 'S') {
                    bfs(grid, new Cello(i, j), path);
                }
            }
        }
        return path;
    }

}

Output is:
Path length:5
{0,0}
{1,0}
{1,1}
{2,1}
{2,2}
{3,2}

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

Can someone help to get Shortest Path with Obstacles?

java

algorithm

breadth-first-search

shortest-path