计算从开始到结束的最短路径，如果我们有能力克服最多 1 个障碍

Question

我们得到了一个二维整数矩阵形式的迷宫；其中 0 是可通过的 space，1 是墙壁。

起始位置始终为：

array[0][0]

，结束位置始终为：

array[HEIGHT -1][WIDTH-1]

唯一可能的移动是向上、向下、向右或向左。考虑到我们最多可以克服迷宫内的一堵墙，我想找到从头到尾的最短路径。我首先创建了一个迷宫 class 和一个顶点 Class。我的第一个想法是使用 BFS，但是，我最近意识到这当然行不通，我现在正在尝试 Dijkstra 的算法。一个想法是给 Wall 的权重比 passible space 昂贵得多，并使用 Dijkstra 找到从开始到结束的最短路径。然后，计算每堵墙到终点的最短路径。在此之后，我想我可以比较墙的路径到尽头，从开始到结束的路径，并以某种方式使用它来决定移除墙是否会给我一条更短的路径。

我真的在与 Dijkstra 作斗争，将所有这些放在一起可能会得到一些有用的东西。我从创建一个迷宫 class 开始，它将采用二维数组输入并从中制作图表。迷宫 Class :

   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;

  }

我的顶点Class :

 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 方法时，出现空指针异常。总而言之，我想我的问题是如何获得从开始到结束的最便宜的路径，然后是墙的路径到结束；每面墙。

Answer 1

使用 Dijkstra 算法构建到任何点的最短路径很好，但是从起点和终点都做。

假设您有这个迷宫，使用 _ 作为 Space，使用 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  _  _  _

如果这让您走到了尽头，那么您就大功告成了，而无需翻墙。
否则，填写距离End的最短距离：

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

计算从开始到结束的最短路径，如果我们有能力克服最多 1 个障碍

Calculate the shortest path from start to end, if we have the ability to overcome at MOST 1 obstacle

java

dijkstra

shortest-path