主题链接：

题意：8个方向的 马跳式走法 ，已知起点 和终点，求最短路

研究了一下双向BFS，不是非常难，和普通的BFS一样。双向BFS只是是从 起点和终点同一时候開始搜索，可降低搜索时间

当两条搜索路线相遇时，结束。

貌似有一年百度的招聘 笔试，就是双向BFS。

。。。

以下，比較一下BFS 和 双向BFS的用时。

BFS

STL的queue可能会浪费一点时间

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          const int N = 310;using namespace std;int mapp[N][N];bool vis[N][N];struct node{    int x,y,ans;};int n;int mv[8][2] = {
    {1,2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1},{-1,2},{-1,-2}};void BFS(int sx,int sy,int ex,int ey){    queue
          
           q; node t,f; memset(vis,0,sizeof(vis)); f.x = sx; f.y = sy; f.ans = 0; vis[sx][sy] = true; q.push(f); while(!q.empty()) { t = q.front(); q.pop(); if(t.x==ex && t.y==ey) { printf("%d\n",t.ans); return ; } for(int i = 0;i<8;i++) { f.x = t.x + mv[i][0]; f.y = t.y + mv[i][1]; if(!vis[f.x][f.y]&& 0<=f.x && f.x 
          
         
        
       
      
     

双向BFS

时间差的不是非常大，可是理论上，时间复杂度会降低若干倍。假设数据大的话，时间差会非常明显

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          const int N = 310;using namespace std;int mapp[N][N];int vis[N][N];struct node{    int x,y;};int n;int mv[8][2] = {
    {1,2},{1,-2},{2,1},{2,-1},{-2,1},{-2,-1},{-1,2},{-1,-2}};int dis[N][N];void BFS(int sx,int sy,int ex,int ey){    if(sx==ex && sy == ey)    {        printf("0\n");        return ;    }    queue
          
           q; node t,f; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); f.x = sx; f.y = sy; t.x = ex; t.y = ey; vis[sx][sy] = 1; //从起点開始搜索的路线 标记为1 vis[ex][ey] = 2; //从终点開始搜索的路线 标记为2 q.push(f); q.push(t); while(!q.empty()) { t = q.front(); q.pop(); for(int i = 0;i<8;i++) { f.x = t.x + mv[i][0]; f.y = t.y + mv[i][1]; if(0<=f.x && f.x 
          
         
        
       
      
     

版权声明：本文博主原创文章。博客，未经同意不得转载。