Может ли кто-нибудь помочь получить кратчайший путь с препятствиями?

Question

У меня есть 2D матрица. Дана двумерная матрица, где некоторые элементы заполнены «1», а остальные элементы заполнены «0», за исключением 2 элементов, один из которых - S (начальная точка) и D (конечная точка). Здесь «0» означает, что вы не можете перейти к этой конкретной точке. Из ячейки вы можете перемещаться влево, вправо, вверх или вниз. Учитывая две точки в матрице, найдите кратчайший путь между этими точками.

Один из кратчайших путей (от S до D, исключая оба): [(3, 2), (3, 1), (2 , 1), (2, 0)]. Вернуть ноль, если между S и D. пути нет.

У меня есть фрагмент кода, который возвращает расстояние от 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). Все, что вам нужно для отслеживания пути, - это поддерживать родительский узел в своем определении узла.

Установите родительский узел начального узла на ноль. Затем, когда вы обнаруживаете узлы в вашей BFS из узла current , установите parent обнаруженного узла в current node.

Теперь, если ваш поиск успешен (т. Е. Вы нажали D в своем поиске), просто проходите цепочку родительских узлов назад от D до тех пор, пока вы не нажмете S, бросая посещенных родителей в стек.

Наконец, просто продолжайте появляться стек, пока он не станет пустым, чтобы получить узлы на пути от S до D.

Answer 2

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}

Answer 3

вы получаете только расстояние, потому что вы только возвращаете расстояние между источником и пунктом назначения. следуйте этим инструкциям, чтобы решить и распечатать маршрут;

al go 1: -

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

al go 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.