使用BFS找到最短路径

正如tittle所说，我试图找到一个单位移动到最近控制点的最短路径（就好像它是一个宝藏或某物）。我试图用BFS来找到这条路，但是它并没有给出最短的路。对于为例：使用BFS找到最短路径

如果我们有这样的事情（其中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; 
}

来源

2014-11-22 aura

我认为这与你如何计算我们以前的矩阵有关。具体如下代码

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

每当你遇到一个不请自来的节点与您正在寻求节点更新之前的矩阵。但是，请考虑一下开始时会发生什么。您将排队开始的每个点，并将每个节点的前一个矩阵标记为起点。现在您将探索其他节点。它们的每一个邻居都将被排队，除了起点之外，因为他们都没有被访问过。前一个矩阵中的一些条目将被覆盖。这就是为什么你的道路没有意义。

来源

2014-11-23 03:29:35 Jfietz

使用BFS找到最短路径

回答

相关问题