Рассчитайте кратчайший путь от начала до конца, если у нас есть способность преодолевать на MOST 1 препятствие

Question

Нам дается лабиринт в виде 2D-матрицы целых чисел; где 0 - пассивное пространство, а 1 - стены.

Исходное положение всегда будет:

array[0][0]

, а конец всегда будет:

array[HEIGHT -1][WIDTH-1]

Единственные возможные перемещения - вверх, вниз, вправо или влево. Я хотел бы найти кратчайший путь от начала до конца, учитывая, что мы можем преодолеть максимум одну стену внутри лабиринта. Я начал с создания класса Maze и класса Vertex. Моя первая мысль заключалась в том, чтобы использовать BFS, однако я недавно понял, что это, конечно, не сработает, и теперь я пытаюсь использовать алгоритм Дейкстры. Идея состоит в том, чтобы придать весу Стены, которая намного дороже, чем пассивное пространство, и использовать Дийкстра, чтобы найти кратчайший путь от начала до конца. Затем вычислите кратчайший путь каждой стены до конца. После этого я думаю, что я могу сравнить пути Стены до конца, с пуском начала до конца, и как-то использовать это, чтобы решить, удалит ли стеновую дверь более короткий путь.

Я действительно борюсь с Дейкстра и все это вместе собираюсь, возможно, получить что-то полезное. Я начал с создания класса Maze, который будет принимать вход 2d-массива и вывести из него график. Maze Класс:

class Maze{ 
    Vertex[][] vertices; 
    ArrayList<Edge> edges; 
    ArrayList<Vertex> walls; 
    HashSet<Vertex> settledVertices; 
    HashSet<Vertex> unsettledVertices; 
    HashMap<Vertex,Integer> distanceMap; 
    HashMap<Vertex,Vertex> predecessors; 

    Vertex start, end; 
    int width; 
    int height; 

//Maze Contructor 
    public Maze(int arr[][]){ 
    this.height = arr.length; 
    this.width = arr[0].length; 
    this.vertices = new Vertex[height][width]; 
    this.edges = new ArrayList<>(); 
    this.walls = new ArrayList<>(); 

    for(int i = 0 ; i < height; i++){ 
     for(int j = 0; j < width; j++){ 
     this.vertices[i][j] = arr[i][j] == 1 ? new Wall(arr[i][j]) : new Vertex(arr[i][j]); 
     if(this.vertices[i][j].value == 1) 
      this.walls.add(this.vertices[i][j]); 
     } 
    } 

    //Build() sets the Edges and their weights, as well as determine each Vertexs neighbors 
    build(); 

    this.start = this.vertices[0][0]; 
    this.end = this.vertices[height-1][width-1]; 

    } 

    //Attempting Dijkstra 
    public void executeDij(Vertex source){ 
    this.settledVertices = new HashSet<>(); 
    this.unsettledVertices = new HashSet<>(); 
    this.distanceMap = new HashMap<>(); 
    this.predecessors = new HashMap<>(); 

    this.distanceMap.put(source,0); 
    this.unsettledVertices.add(source); 

    while(unsettledVertices.size() > 0){ 
     Vertex v = getMinimum(unsettledVertices); 
     unsettledVertices.remove(v); 
     findMinDistance(v); 
    } 
    } 


    public int getDistance(Vertex arrow, Vertex target){ 
     for(Edge e : edges) 
     if(e.source.equals(arrow) && e.destination.equals(target)) 
     return e.weight; 

    throw new RuntimeException("Get distance error"); 
    } 




    public void findMinDistance(Vertex vertex){ 
     for (Vertex target : vertex.neighbors) { 
     if(getShortestDistance(target) > getShortestDistance(vertex) + getDistance(vertex, target)) 
      distanceMap.put(target, getShortestDistance(vertex) + getDistance(vertex,target)); 
     } 

    } 




    public int getShortestDistance(Vertex destination){ 
    Integer d = distanceMap.get(destination); 

    if(d == null) 
     return Integer.MAX_VALUE; 
    return d; 
    } 



    public Vertex getMinimum(HashSet<Vertex> set){ 
    Vertex min = null; 

    for(Vertex v : set){ 
     if(min == null){ 
     min = v; 
     }else{ 
     if(getShortestDistance(v) < getShortestDistance(min)){ 
     min = v; 
     }  
     } 
    } 
    return min; 
    } 



    public boolean isSettled(Vertex v){ 
    return settledVertices.contains(v); 
    } 



    public LinkedList<Vertex> getPath(Vertex target){ 
    LinkedList<Vertex> path = new LinkedList<>(); 
    Vertex singleStep = target; 

    if(predecessors.get(singleStep) == null) 
     return null; 

    path.add(singleStep); 

    while(predecessors.get(singleStep) != null){ 
     singleStep = predecessors.get(singleStep); 
     path.add(singleStep); 
    } 

    Collections.reverse(path); 
    return path; 

    } 

Мой Vertex Класс:

class Vertex{ 
    int value; 
    boolean visited; 
    int distance; 
    Vertex previous; 
    ArrayList<Vertex> neighbors = new ArrayList<>(); 

    public Vertex(int value){ 
     this.value = value; 
    } 

    public boolean isWall(){ 
     return this.value == 1; 
    } 

    public void setVisited(){ 
     this.visited = true; 
    } 

    public int getValue(){ 
     return this.value; 
    } 

} 

Я в основном потерял себя в этот момент, и я не уверен, что я даже делать больше. Когда я пытаюсь использовать мой метод getPath, я получаю исключение Null Pointer. В целом, я думаю, мой вопрос в том, как я могу получить наименее дорогой путь от начала до конца, а затем путь к стенам до конца; для каждой Стены.

Answer 1

Использование алгоритма Дейкстры для построения кратчайшего пути к любой точке является хорошим, но делать это как от начала, так и от конца.

Допустим, у вас есть этот лабиринт, используя _ для пространства и X для стены:

s _ _ X _ _ 
X _ X X _ X 
_ _ X _ _ _ 
_ X _ _ X _ 
_ X X _ X _ 
_ _ X _ _ e 

Во-первых, заполнить кратчайшее расстояние от начала:

s s1 s2 X _ _ 
X s2 X X _ X 
s4 s3 X _ _ _ 
s5 X _ _ X _ 
s6 X X _ X _ 
s7 s8 X _ _ _ 

Если у вас до конца , вы закончите без необходимости прыгать через стену.
В противном случае, заполнить кратчайшее расстояние от Конца:

s s1 s2 X e6 e7 
X s2 X X e5 X 
s4 s3 X e5 e4 e3 
s5 X e5 e4 X e2 
s6 X X e3 X e1 
s7 s8 X e2 e1 e 

Теперь найти стены, которые находятся рядом с начальным значением и конечным значением:

s s1 s2 -- e6 e7 
X s2 X X e5 X 
s4 s3 -- e5 e4 e3 
s5 -- e5 e4 X e2 
s6 X X e3 X e1 
s7 s8 -- e2 e1 e 

Выберите стену с наименьшей суммы два расстояния.
Из 4 кандидатов, 3 имеют сумму 8 и 1 имеет сумму 10.
Есть здесь в общей сложности 5 решений:

s →s1→s2→--→e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 │ s →s1 s2 -- e6 e7 
      ↓↓ │ ↓↓    │ ↓↓    │ ↓↓    │ ↓↓    
X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X │ X s2 X X e5 X 
      ↓↓ │ ↓↓    │ ↓↓    │ ↓↓    │ ↓↓    
s4 s3 -- e5 e4→e3 │ s4 s3→--→e5→e4→e3 │ s4 s3→--→e5 e4 e3 │ s4 s3→-- e5 e4 e3 │ s4 s3 -- e5 e4 e3 
       ↓↓ │    ↓↓ │   ↓↓  │  ↓↓   │ ↓↓   
s5 -- e5 e4 X e2 │ s5 -- e5 e4 X e2 │ s5 -- e5 e4 X e2 │ s5 -- e5→e4 X e2 │ s5 --→e5→e4 X e2 
       ↓↓ │    ↓↓ │   ↓↓  │   ↓↓  │   ↓↓  
s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 │ s6 X X e3 X e1 
       ↓↓ │    ↓↓ │   ↓↓  │   ↓↓  │   ↓↓  
s7 s8 -- e2 e1 e │ s7 s8 -- e2 e1 e │ s7 s8 -- e2→e1→e │ s7 s8 -- e2→e1→e │ s7 s8 -- e2→e1→e