如何在国王的最短路径的国际象棋棋盘上做BFS？

我已经在标准国际象棋坐标中给出了一个源索引和一个目标索引。现在我必须打印从源到目的地的最短路径。如何在国王的最短路径的国际象棋棋盘上做BFS？

#include <iostream> 
#include <queue> 
#include <string.h> 
using namespace std; 
int dx[]={1,1,1,-1,-1,-1,0,0}; 
int dy[]={1,0,-1,1,0,-1,1,-1}; 
int cost[10][10]; 
int parent[70]; 
bool visited[70]; 
int main() 
{ 
    memset(parent,-1,sizeof parent); 
    memset(visited,0,sizeof visited); 
    memset(cost,255,sizeof cost); 
    char a,b; 
    cin>>a>>b; 
    int s1 = a-'a',s2 = b-'0'-1; 
    cin>>a>>b; 
    int t1 = a-'a',t2 = b-'0'-1; 
    queue<int> q; 
    q.push(s1*8 + s2); 
    visited[s1*8+s2] = true; 
    cost[s1][s2] = 0; 
    while(!q.empty()) 
    { 
     int u = q.front(),x=u/8,y=u%8; 
     q.pop(); 
     for(int i=0;i<8;++i) 
     { 
      int vx = x+dx[i]; 
      int vy=y+dy[i]; 
      int v = vx*8+vy; 
      if(vx<0 ||vy<0 || vx>=8 ||vy >=8) 
       continue; 
      visited[v] = true; 
      parent[v] = u; 
      q.push(v); 

     } 
    } 
    int t = t1*8+t2; 
    while(parent[t]!=(-1)) 
    { 
     cout<<t/8<<" "<<t%8<<endl; 
     t = parent[t]; 
    } 
}

但是，当我输入运行它像a8 h1的路径不是最短路径，而一个很长的路。我如何找到最短路径？

来源

2014-01-13 Unbound

您的BFS停止条款在哪里？

你的主回路应break一旦你找到x == t1 && y == t2
或者，您也可以修改parent[v]只有visited[v]已经如此。
（如果您只想要最短路径，第一个选项通常会更好）。

否则，您将继续开发更多路径，并覆盖到每个节点的最短路径。

来源

2014-01-13 17:50:01 amit

如果您访问一个节点，这意味着已找到最短路径（因为您的图不是加权的），您不应该多次更新访问阵列的单个条目。我也看不到你如何处理对同一个节点的多次访问。看起来你忘了使用成本阵列。

来源

2014-01-13 17:38:41 nikitoz

首先，BFS不需要'cost'数组。 – amit

@amit，你是对的 – nikitoz

Lee算法可能有所帮助：https://en.wikipedia.org/wiki/Lee_algorithm。这是一种在矩阵中获得最短路径的bfs方式。

来源

2017-01-23 12:03:26

OP的代码是[Dijkstra算法]（https://en.wikipedia.org/wiki/Dijkstra's_algorithm）的实现，它基本上是一样的东西，但是使用队列来处理wave扩张步骤。 – Rup

我看到了...我想指出的是，已经有一个众所周知的在矩阵中解决这个问题的算法/方法，而不是特别涉及图论。 –

如何在国王的最短路径的国际象棋棋盘上做BFS？

回答

相关问题