Knight Moves（裸奔BFS）

搜索

• 题面链接
  Description

  给出骑士的初始位置和目标位置，计算骑士至少要走多少步才能到达目标位置。他的移动方式遵守国际象棋马的走法。

  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。

• 代码

#include<stdio.h>
#include<queue>
#include<string.h>
#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];//标记该点是否走过
int i,j,x,y,ex,ey,num;//ex，ey表示终点坐标，num表示最少走的步数
char a[3],b[3];
struct node
{
    int x,y,step;
};
int BFS()
{
    node now,next;
    queue<node>q;
    now.x=x;
    now.y=y;
    now.step=0;
    if(now.x==ex&&now.y==ey)
        return now.step;
    q.push(now);
    memset(vis,0,sizeof(vis));
    vis[x][y]=1;//标记是否走过，同时记录从起点到该点走的最小步数（vis起点的值没有实际意义，只是用来标记）
    while(!q.empty())
    {
        now=q.front();//取出队首
        q.pop();//队首出队
        if(now.x==ex&&now.y==ey)
        {
            return vis[now.x][now.y];
        }
        for(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)//边界和条件
            {
                next.step=now.step+1;
                vis[next.x][next.y]=next.step;
                q.push(next);
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%s%s",a,b))
    {
        x=a[0]-'a'+1;
        y=a[1]-'0';
        ex=b[0]-'a'+1;
        ey=b[1]-'0';
        num=BFS();
        printf("To get from %s to %s takes %d knight moves.\n",a,b,num);
    }
    return 0;
}