Knight Moves(骑士移动) (bfs经典模板题) POJ-2243

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.
Input
The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying “To get from xx to yy takes n knight moves.”.
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.
您的一位朋友正在研究旅行骑士问题 (TKP)，您将在其中找到最短的封闭式骑士移动旅行，该旅行只访问棋盘上给定的一组 n 个方格中的每个方格一次。他认为这个问题最困难的部分是确定两个给定方格之间的最小骑士移动次数，一旦你完成了这一点，就很容易找到巡回赛。
你当然知道反之亦然。所以你让他写一个解决“困难”部分的程序。

您的工作是编写一个程序，将两个正方形 a 和 b 作为输入，然后确定从 a 到 b 的最短路径上的骑士移动次数。
输入
输入将包含一个或多个测试用例。每个测试用例由一行包含两个由一个空格分隔的正方形组成。正方形是棋盘上由代表列的字母（ah）和代表行的数字（1-8）组成的字符串。
输出
对于每个测试用例，打印一行说“从 xx 到 yy 需要 n 个骑士移动。”。
样本输入
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
样本输出
从 e2 到 e4 需要 2 个骑士移动。
从 a1 到 b2 需要 4 次骑士移动。
从 b2 到 c3 需要 2 个骑士移动。
从 a1 到 h8 需要6个骑士移动。
从 a1 到 h7 需要 5 个骑士移动。
从 h8 到 a1 需要 6 个骑士移动。
从 b1 到 c3 需要 1 个骑士移动。
从 f6 到 f6 需要 0 个骑士移动。

中文大意

题意描述：输入一组为多实例的数据，每组测试数据共有两个字符串，都是字母加数字的形式，代表骑士的起点坐标和终点坐标，棋盘有a-h行和1-8列，要求输出骑士从起点到终点所需要的最小移动步数。

解题思路：利用bfs广搜思想，让骑士按照特定方向运动，每到一个点就标记一个点。

错误分析：注意骑士的运动方式，每到一个点之后共有八种运动方向，和中国象棋中的马的移动方式一样。

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
struct note{
	int x;
	int y;
	int s;
};//利用结构体定义x，y，s

int main()
{
	struct note mp[70];//最多8*8个地图元素
	int a[9][9]={0},book[9][9]={0};//利用book进行标记
	int next[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};//定义移动方式
    int h,t;
    int i,j,k,stx,sty,p,q,tx,ty,flag;
    char c1[10],c2[10];
    
    for(i=1; i<=8; i++)
    	for(j=1; j<=8; j++)
    		a[i][j]=0;//输入地图
	while(cin>>c1>>c2)
	{
		memset(book,0,sizeof(book));//置零
		stx=c1[0]-'a'+1;
		p=c2[0]-'a'+1;
		sty=c1[1]-'0';
		q=c2[1]-'0';//将字母转换为坐标
	if(stx==p&&sty==q)//起点终点相同，输出0
	    printf("To get from %s to %s takes %d knight moves.\n",c1,c2,0);
	else
	{
		h=1;t=1;//定义头和尾
		mp[t].x =stx;
		mp[t].y =sty;
		mp[t].s =0;
		t++;
		book[stx][sty]=1;标记为走过，防止重复计入
		flag=0;
		while(h<t)
		{
			for(k=0; k<8; k++)
			{
				tx=mp[h].x +next[k][0];
				ty=mp[h].y +next[k][1];//进行搜索
				if(tx<1||tx>8||ty<1||ty>8)//防止搜索到地图外
				    continue;
				if(a[tx][ty]==0&&book[tx][ty]==0)
				{
					book[tx][ty]=1;
					mp[t].x =tx;
					mp[t].y =ty;
					mp[t].s =mp[h].s +1;//找到就存如
					t++;
				}
				if(tx==p&&ty==q)
				{
					flag=1;
					break;
				}
			}
			if(flag==1)
			    break;
			h++;
		}
	printf("To get from %s to %s takes %d knight moves.\n",c1,c2,mp[t-1].s );
	}
	}
	return 0;
}