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

我们以2D整数矩阵的形式给出了一个迷宫;其中0是可通空间，1是墙 .

起始位置始终是：

array[0][0]

并且结尾将始终为：

array[HEIGHT -1][WIDTH-1]

唯一可能的移动是向上，向下，向右或向左 . 我想找到从开始到结束的最短路径，考虑到我们最多可以克服迷宫内的一面墙 . 我开始创建一个Maze类和一个Vertex类 . 我的第一个想法是使用BFS，但是，我最近意识到这当然不会起作用，我现在正在尝试Dijkstra _2458706的重量比可通行空间大得多，并使用Dijkstra 's to find the shortest path from start to finish. Then, calculate each Wall'的最短路径到最后 . 在此之后，我想我可以比较墙壁到最后的路径，从开始到结束的路径，并以某种方式使用它来决定移除墙壁是否会给我一条较短的路径 .

我真的在与Dijkstra挣扎，把所有这些放在一起，或许能得到一些有用的东西 . 我开始创建一个Maze类，它将采用2d数组输入并从中创建一个图形 . 迷宫课程：

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 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方法时，我得到一个空指针异常 . 总而言之，我想我的问题是如何从开始到结束获得最便宜的路径，然后是墙到达终点的路径;为每一面墙 .