MOST 1 장애물에서 극복 할 수있는 능력을 가진 경우 시작부터 끝까지 최단 경로를 계산하십시오.

Question

우리는 2 차원 정수 형태로 미로를 제공합니다. 여기서 0은 무시할 수있는 공간이고 1은 벽입니다.

시작 위치는 항상

array[0][0]

이고 끝은 항상 다음과 같습니다.

array[HEIGHT -1][WIDTH-1]

가능한 동작은 위, 아래, 오른쪽 또는 왼쪽입니다. 미로 내부에 최대 1 개의 벽을 극복 할 수 있다고 생각하면서 처음부터 끝까지 최단 경로를 찾고 싶습니다. 나는 Maze 클래스와 Vertex 클래스를 작성하여 시작했습니다. 나의 첫 번째 생각은 BFS를 사용하는 것이었지만, 나는 이것이 물론 작동하지 않을 것이라는 것을 최근에 깨달았고, 이제 나는 Dijkstra 's Algorithm을 시도하고있다. 아이디어는 무한한 공간보다 훨씬 더 비싼 Wall의 가중치를 제공하고 Dijkstra 's를 사용하여 처음부터 끝까지 최단 경로를 찾는 것입니다. 그런 다음 각 Wall의 최단 경로를 계산합니다. 이 후, 나는 벽의 경로를 끝과 끝의 경로를 비교할 수 있다고 생각하고, 벽을 제거하면 더 짧은 경로를 줄 것인지 어떻게 든 결정할 수있다.

저는 Dijkstra와 정말 고심하고 있으며이 모든 것을 모아 유용하게 사용할 수 있습니다. Maze 클래스를 만드는 것으로 시작했는데, 2 차원 배열 입력을 받아 그래프를 만들었습니다. 미로 클래스 :

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 메서드를 사용하려고하면 Null 포인터 예외가 발생합니다. 결국, 나의 질문은 내가 시작부터 끝까지 가장 비싼 길을 얻는 방법, 그리고 끝으로 벽의 길을 얻을 수 있다는 것이다. 각 벽마다.

Answer 1

Dijkstra 's 알고리즘을 사용하여 어떤 지점에 대한 최단 경로를 작성하는 것이 좋지만 시작과 끝 모두에서 수행하십시오.

의 당신이 벽을위한 공간에 대한 _ 및 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 5 개 솔루션의 총 여기에 있습니다 합계 10
있습니다

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