HDU 1372【Knight Moves】

描述

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

大意

在一个8*8的棋盘上，一只中国象棋中的马要从一个点跳到另一个点。问最少需要多少步。

输入输出格式

输入

整个测试组由多组数据组成，请做到文件底结束。
对于每组数据，前两个坐标代表出发点，后两个代表结束点。注意坐标第一位为a至h中某个字母，第二位为1到8某个数字。

输出

对于每个测试请输出"To get from xx to yy takes n knight moves.".

输入输出样例

输入样例

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

输出样例

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.

解题思路

　　先输入字符串，再转换成int坐标，然后八个方向慢慢搜。

题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string x,y;
 4 int sx,sy,ex,ey;
 5 int mp[9][9];//记录最少步数 
 6 const int dir[8][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};//八个方案 
 7 struct node{
 8     int X;
 9     int Y;//坐标 
10     node(){}
11     node(int xx,int yy)
12     {
13         X=xx;
14         Y=yy;
15     }
16 };
17 queue<node> q;
18 void bfs()
19 {
20     q.push(node(sx,sy));
21     mp[sx][sy]=0;
22     while(!q.empty())
23     {
24         node head=q.front();//队头 
25         q.pop();
26         if(head.X==ex&&head.Y==ey)//达到了 
27         {
28             cout<<"To get from "<<x<<" to "<<y<<" takes "<<mp[ex][ey]<<" knight moves."<<endl;//输出答案 
29             break;
30         }
31         for(int i=0;i<8;i++)//八个方向 
32         {
33             int tx=head.X+dir[i][0];
34             int ty=head.Y+dir[i][1];
35             if(tx>=1&&tx<=8&&ty>=1&&ty<=8&&mp[tx][ty]==-1)//判断合法 
36             {
37                 mp[tx][ty]=mp[head.X][head.Y]+1;//记录 
38                 q.push(node(tx,ty));//继续搜索 
39             }
40         }
41     }
42     while(!q.empty())
43     {
44         q.pop();//清空队列 
45     }
46 }
47 int main()
48 {
49     while(cin>>x>>y)
50     {
51         for(int i=1;i<=8;i++)
52         {
53             for(int j=1;j<=8;j++)
54             {
55                 mp[i][j]=-1;//赋初值 
56             }
57         }
58         sx=x[0]-'a'+1;
59         sy=x[1]-'0';
60         ex=y[0]-'a'+1;
61         ey=y[1]-'0';//转换操作 
62         bfs();
63     } 
64     return 0;
65 }