BFS를 사용하여 최단 경로 찾기

Question

작은 자릿수가 말하듯이, 내가 보물이라도되는 것처럼 neareast 제어점으로 이동하는 최단 경로를 찾으려고합니다. 이 경로를 찾기 위해 BFS를 사용하려고했지만 최단 경로를 제공하지 않습니다. exemple의 경우 :

· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · - - - · · · · · · · 
· · | X | · · · · · · · 
· · | | - · · · · · · · 
· · | · · · · · · · · · 
· · | · · · · · · · · · 
· · · | · · · · · · · · 
· · · | - K · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 

하지만 돈 : 우리가 이런 일이 (X는 시작 위치이며, K는 하나의 제어 포인트입니다) 경우

는

· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · X · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · K · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 
· · · · · · · · · · · · 

내 코드는이 경로를 제공 왜 내가 그 여분의 움직임을주는 지 알지 못한다. 누군가 내가 뭘 잘못하고 있는지 말할 수 있니?

typedef pair<int,int> Coord; 
typedef vector< vector<bool> > VIS; 
typedef vector<vector< Coord> > Prev; 
const int X[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; 
const int Y[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }; 


list<Coord> BFS2(int x, int y, VIS& visited, Prev& p) { 
    queue<Coord> Q; 

    Coord in; 
    in.first = x; in.second = y; 

    Q.push(in); 
    bool found = false; 
    Coord actual; 
    while(not Q.empty() and not found){ 
     actual = Q.front();   
     Q.pop(); 
     int post = who_post(actual.first, actual.second); //It tells if we're in a control point or not(0 == if we are not in the C.point) 
     if(post != 0){ 
      found = true;     
     } 
     else { 
      visited[actual.first][actual.second]=true; 
      for(int i = 0; i < 8; i++){ 
        int nx = X[i] + actual.first;  
        int ny = Y[i] + actual.second; 
       //The maze is 60x60, but the borders are all mountains, so we can't access there 
       if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){ 
        Coord next; 
        next.first = nx; next.second = ny; 
        Q.push(next); 
        p[nx][ny] = actual; 
       } 
      } 
     } 
    } 
    list<Coord> res; 

    while(actual != in){ 
     res.push_back(actual); 
     actual = p[actual.first][actual.second]; 
    } 
    res.reverse(); 
    return res; 
} 

Answer 1

이전 매트릭스를 계산하는 방법과 관련이 있다고 생각합니다. 특히 다음 코드

if(nx>=1 and nx<59 and ny>=1 and ny<59 and not visited[nx][ny]){ 
    ... 
    p[nx][ny] = actual; 
} 

현재 탐색중인 노드로 초대되지 않은 노드를 발견 할 때마다 이전 매트릭스를 업데이트합니다. 그러나 시작하면 어떻게 될지 고려하십시오. 시작하는 지점의 모든 지점을 대기열에 넣고 각 노드의 이전 매트릭스를 시작점으로 표시합니다. 이제 다른 노드를 살펴 보겠습니다. 각 이웃은 방문한 사람이 없으므로 시작점을 제외하고는 대기열에 들어갑니다. 이전 매트릭스의 엔트리 중 일부는 덮어 쓰기됩니다. 이것이 당신의 길을 이해하지 못하는 이유입니다.