如何在國王的最短路徑的國際象棋棋盤上做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？

回答

相關問題