主题链接：Knight Moves

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

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

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

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

。。。

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

BFS

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

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

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<node>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 <n && 0<=f.y && f.y<n)

            {

                f.ans = t.ans + 1;

                q.push(f);

                vis[f.x][f.y] = true;

            }

        }

    }

}

int main()

{

    int t,sx,sy,ex,ey;

    std::ios::sync_with_stdio(false);

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        scanf("%d%d",&sx,&sy);

        scanf("%d%d",&ex,&ey);

        BFS(sx,sy,ex,ey);

    }

    return 0;

}

双向BFS

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2p3MDEzMA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">

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

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

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<node>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 <n && 0<=f.y && f.y<n)

            {

                if(!vis[f.x][f.y])

                {

                dis[f.x][f.y] = dis[t.x][t.y] + 1;

                q.push(f);

                vis[f.x][f.y] = vis[t.x][t.y];

                }

                else if(vis[f.x][f.y]!=vis[t.x][t.y]) //两者相遇

                {

                    printf("%d\n",dis[f.x][f.y]+dis[t.x][t.y] + 1); //会漏掉相遇的那个点，所以要加1

                    return ;

                }

            }

        }

    }

}

int main()

{

    int t,sx,sy,ex,ey;

    std::ios::sync_with_stdio(false);

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        scanf("%d%d",&sx,&sy);

        scanf("%d%d",&ex,&ey);

        BFS(sx,sy,ex,ey);

    }

    return 0;

}