BFS之五(双向bfs)

#include <iostream>            //poj 2243 Knight Moves  参照poj 1915#include <deque>using namespace std;int dir[2][8]={{-2,-1,1,2,2,1,-1,-2},{-1,-2,-2,-1,1,2,2,1}};int visited[10][20],path[10][20];struct node{    int x,y,c;    bool operator==(const node& other)    {        return x==other.x&&y==other.y;    }    node(int xx=0,int yy=0,int cc=0)    {        c=cc;x=xx;y=yy;    }};deque<node> forword,backword;int main(){    //freopen("F:\\c++.txt", "r", stdin ) ;    char in[10];    int x,y,c,tx,ty;    while(gets(in))    {        memset(visited,0,sizeof(visited));        memset(path,0,sizeof(path));        node beg(int(in[1]-48),int(in[0]-96)),end(int(in[4]-48),int(in[3]-96));        if(beg==end)        {            printf("To get from %c%c to %c%c takes 0 knight moves.\n",in[0],in[1],in[3],in[4]);            continue;        }        visited[beg.x][beg.y]=1;visited[end.x][end.y]=2;        forword.clear();backword.clear();        backword.push_back(end);forword.push_back(beg);        char tag=0;        while(!tag&&!forword.empty())        {            node nd1=forword.front();            forword.pop_front();            x=nd1.x;y=nd1.y;c=nd1.c+1;                for(int i=0;i<8;++i)            {                tx=x+dir[0][i];                ty=y+dir[1][i];                if(tx<1||tx>8||ty<1||ty>8)                    continue;                if(visited[tx][ty]==0)                {                    path[tx][ty]=c;                    visited[tx][ty]=1;                    node t(tx,ty,c);                    forword.push_back(t);                }                else if(visited[tx][ty]==2)                {                    printf("To get from %c%c to %c%c takes %d knight moves.\n",in[0],in[1],in[3],in[4],c+path[tx][ty]);                    tag=1;break;                }            }            if(tag)                break;            if(!backword.empty())            {                node nd2=backword.front();                backword.pop_front();                x=nd2.x;y=nd2.y;c=nd2.c+1;                for(int i=0;i<8;++i)                {                    tx=x+dir[0][i];                    ty=y+dir[1][i];                    if(tx<1||tx>8||ty<1||ty>8)                        continue;                    if(visited[tx][ty]==0)                    {                        path[tx][ty]=c;                        visited[tx][ty]=2;                        node t(tx,ty,c);                        backword.push_back(t);                    }                    else if(visited[tx][ty]==1)                    {                        printf("To get from %c%c to %c%c takes %d knight moves.\n",in[0],in[1],in[3],in[4],c+path[tx][ty]);                        tag=1;break;                    }                }            }        }    }    return 0;}

原文链接: https://www.cnblogs.com/mjc467621163/archive/2011/08/22/2149144.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍