Uva 439 Knight Moves

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380

题目大意是在一个网格中（行编号从1~8，列编号从a~h），给你两个点，要你找出象棋中的马从一个点跳到另一个点的最少步数。是一道十分基础的bfs（宽度优先搜索）。

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

struct Point
{
	int x,y,step;
	bool operator == (const Point &b)
	{
		if(x==b.x&&y==b.y) return 1;
		else return 0;
	}
};
int bfs(Point a,Point b)
{
	queue<Point> q;
	if(a==b) return 0;
	q.push(a);
	while(!q.empty())
	{
		Point cur=q.front();
		q.pop();
		if(cur==b) return cur.step;
		int dir[8][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};//马跳跃的八个方向
		for(int i=0;i<8;i++)
		{
			Point next;
			next.x=cur.x+dir[i][0];
			next.y=cur.y+dir[i][1];
			next.step=cur.step+1;
			if(next.x<1||next.x>8||next.y<1||next.y>8) continue;//判断越界
			q.push(next);
		}
	}
	return -1;//马一定可以跳到终点，所以这只是一个形式
}
int main()
{
	string str1,str2;
	Point a,b;
	while(cin>>str1>>str2)
	{
		a.y=str1[0]-'a'+1;//先把字母转换成数字
		a.x=str1[1]-'0';
		a.step=0;
		b.y=str2[0]-'a'+1;
		b.x=str2[1]-'0';
		int ans=bfs(a,b);
		cout<<"To get from "<<str1<<" to "<<str2<<" takes "<<ans<<" knight moves."<<endl;
	}
	return 0;
}