Java- Maze Breadth 첫 번째 검색 최단 경로

Question

구현하고있는 첫 번째 검색 알고리즘에 의해 발견 된 최단 경로를 검색하는 방법에 문제가있는 것 같습니다. 현재 알고리즘은 그것이 도달 할 수 있다면 미로의 출구를 찾을 수 있기 때문에 작동합니다. 다른 게시물에서 노드가 방문한 것으로 표시된 후에 부모의 압정을 지키는 사람이 언급되었습니다. Point 구조 안에 부모 Point를 포함하여 부모를 추적하는 간단한 구현을 시도했지만 지금까지 traveresed 한 모든 경로를 표시하는 Grid의 경로를 Mark 할 때 나는 엉망이되었을 수도 있습니다. 어쨌든 부모님의 기록을 지켜라.

내가 잘못한 부분에 대해서는 단서가 있습니다. 어쩌면 나는 간단한 것을 놓치고 있습니까? 코드는 아래 참고 자료로 포함되어 있습니다.

미로는 2D 정수 격자입니다. 1이 벽이고 0이 이동 가능한 경로라고 가정합니다.

포인트 클래스에는 다음이 포함됩니다. 포인트 부모 int x, y; 아무것도 더.

public Point BFS(int x, int y){ 
    Queue<Point> Path = new Queue<>(); 

    Path.enqueue(new Point(x,y));//push current on queue 

    Point Cur = Path.front();//make current point 
    //test code for recursive backcall of path 
     Cur.setParent(null); 
    //test code for recursive backcall of path 


    Point end = new Point(mWidth-2, mHeight-2);//set goal 

    while((!Path.isEmpty())){ 
     Point old = Cur; 

     Cur = Path.dequeue(); 
     Cur.setParent(old); 

     if(Cur.compareto(end)){ 
      return Cur;//return Point then traverse up from here calling Cur.Parent to get path. 
     } 
     else if(Maze[Cur.getX()][Cur.getY()]==1){//Enque all possible paths 

      Maze[Cur.getX()][Cur.getY()] = 2;//mark as visitied 
      if(Cur.getX()-1>=0) 
       if(Maze[Cur.getX()-1][Cur.getY()]==1) 
        Path.enqueue(new Point(Cur.getX()-1,Cur.getY())); 

      if(Cur.getX()+1<mWidth) 
       if(Maze[Cur.getX()+1][Cur.getY()]==1) 
        Path.enqueue(new Point(Cur.getX()+1,Cur.getY())); 

      if(Cur.getY()-1>=0) 
       if(Maze[Cur.getX()][Cur.getY()-1]==1) 
        Path.enqueue(new Point(Cur.getX(),Cur.getY()-1)); 

      if(Cur.getY()+1<mHeight) 
       if(Maze[Cur.getX()][Cur.getY()+1]==1) 
        Path.enqueue(new Point(Cur.getX(),Cur.getY()+1)); 
     } 

    } 
    return null; 
} 

Answer 1

old은 더 이상 여러 번 반복 한 후에 부모가 아닙니다. 그런 다음

Point next = new Point(Cur.getX()-1,Cur.getY()); 
next.setParent(Cur); 
Path.enqueue(next); 

당신은 끝을 찾을 때, 당신이 때까지의 getParent()를 호출하여 다시 시작 경로를 얻을 수 있어야합니다 : 예를 들어, 대신에 큐 포인트를 추가 할 때 당신은 부모를 설정할 수 있습니다 null.