Knight Moves------一个简单的bfs

Time Limit:1000MS  Memory Limit:32768KB  64bit IO Format:%I64d & %I64u

BFS

来源：HDU1372 Knight Moves

Description

在象棋王国，尼古拉斯.火山是一匹英俊的马，他非常幸运迎娶了白马王国的公主，他们将度蜜月，你现在是他们的女仆，火山会问你去一些地方最少需要多少步，这么简单的事当然难不倒你。由于火山是一匹马，他的移动方式将会遵守国际象棋马的走法。 输入： 输入包含一个或多个输入样例。每个测试样例将会有两个坐标，表示现在的位置和将要到达的地方，每个坐标包含一个字母（a-h）表示列和一个数字(1-8) 行，这意味这这个象棋王国是一个8* 8的矩形。

Input

输入包含一个或多个输入样例。每个测试样例将会有两个坐标，表示现在的位置和将要到达的地方，每个坐标包含一个字母（a-h）表示列和一个数字(1-8) 行，这意味这这个象棋王国是一个8* 8的矩形。

Output

每一组样例将会输出一段话 "To get from xx to yy takes n knight moves."，其中xx表示起点，yy表示终点，n为xx到yy的最短步数。

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

BFS代码：

int bfs()
{
    node now,next;
    queue<node>q;
    now.x=x1;
    now.y=y1;
    now.step=0;
    vis[x1][y1]=1;
    if(now.x==x2&&now.y==y2)
        return now.step;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==x2&&now.y==y2)
            return now.step;
        for(int i=0;i<8;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x>0&&next.x<=8&&next.y>0&&next.y<=8&&vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}

完整代码：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int dir[8][2]={1,2,-1,2,-1,-2,1,-2,2,1,-2,-1,-2,1,2,-1};//方向数组
int vis[10][10];//标记数组
char a[10],b[10];//存起点终点
int x1,x2,y1,y2;//起点与终点
struct node
{
    int x,y,step;
};
int bfs()
{
    node now,next;
    queue<node>q;
    now.x=x1;
    now.y=y1;
    now.step=0;
    vis[x1][y1]=1;
    if(now.x==x2&&now.y==y2)
        return now.step;
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        if(now.x==x2&&now.y==y2)
            return now.step;
        for(int i=0;i<8;i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(next.x>0&&next.x<=8&&next.y>0&&next.y<=8&&vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                next.step=now.step+1;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    while((scanf("%s%s",a,b))!=EOF)
    {
        x1=a[1]-'0';//！注意！字母与数字之间的转换，下同
        y1=a[0]-'a'+1;
        x2=b[1]-'0';
        y2=b[0]-'a'+1;
        memset(vis,0,sizeof(vis));
        int t=bfs();
          printf("To get from %s to %s takes %d knight moves.\n",a,b,t);
    }
    return 0;
}