#include<iostream>
#include<queue>
using namespace std;

int x[8] = {1,2,2,1,-1,-2,-2,-1};
int y[8] = {2,1,-1,-2,-2,-1,1,2};

typedef struct
{
	int xx;
	int yy;
	int deep;
}Map;

int visit[10][10];
int BFS(Map v, Map u)
{
	int count = 0;
	Map str;
	str.deep = v.deep = 0;
	queue<Map> Q;		//	构建队列
	Q.push(v);			//	顶点入队
	visit[v.xx][v.yy] = 1;

	while(!Q.empty())	//	队列非空
	{
		v = Q.front();	//	访问队首元素

		if(v.xx == u.xx  &&  v.yy == u.yy)	//	达到条件
			return v.deep;
		for(int i = 0; i < 8; ++ i)
		{
			str.xx = v.xx + x[i];
			str.yy = v.yy + y[i];
			if(visit[str.xx][str.yy] || str.xx<0 || str.xx>8 || str.yy<1 || str.yy>8)
				continue;

			str.deep = v.deep +1;
			Q.push( str );	//	按条件添入队列
			visit[str.xx][str.yy] = 1;
		}
		Q.pop();		//	对头出队
	}
}
int main()
{
	char A[2],B[2];
	while(scanf("%s %s",&A,&B) != EOF)
	{
		Map str1, str2;
		memset(visit,0,sizeof(visit));
		str1.xx = A[0]-'a',	str1.yy = A[1]-'0';
		str2.xx = B[0]-'a',	str2.yy = B[1]-'0';
		int c = BFS(str1,str2);
		cout<<"To get from "<<A<<" to "<<B<<" takes "<<c<<" knight moves."<<endl;
	}
	return 0;
}

• Re:求大神指导，样例全过WA (160) penghaitao 2014-08-12 09:47:37