poj2243 跳馬問題，bfs一下就可以了。

<pre name="code" class="cpp">#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;


char a[3],b[3];
int vis[8][8],m;
int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};


struct node
{
int x,y;
}p1,p2,d[8];


queue<node>pai;


bool operator ==(node q,node p)
{
if(q.x==p.x&&q.y==p.y)return true;
else return false;
}


node operator+(node q,node p)
{
node qq;
qq.x=q.x+p.x;
qq.y=q.y+p.y;
return qq;
}


bool pan(int x,int y)
{
if(x>=0&&x<8&&y>=0&&y<8&&!vis[x][y])
{
vis[x][y]=1;
return true;
}
else return false;
}
bool bfs(node end)
{
node s,ss;
int t=-1;
while(!pai.empty())
{ 
int l=pai.size();t++;
for(int i=0;i<l;i++)
{
s=pai.front();
if(s==end){m=t;return true;}
pai.pop();
for(int i=0;i<8;i++)
{
ss=s+d[i];
if(pan(ss.x,ss.y))
pai.push(ss);
}
}
}
return false;
}


int main()
{
//freopen("t.txt","r",stdin);
int i;
for(i=0;i<8;i++)
{
d[i].x=dx[i];
d[i].y=dy[i];
}
while(scanf("%s %s",&a,&b)!=EOF)
{
memset(vis,0,sizeof(vis));
p1.x=a[0]-'a';p1.y=a[1]-'1';
p2.x=b[0]-'a';p2.y=b[1]-'1';
while(!pai.empty())pai.pop();
m=0;pai.push(p1);
if(!bfs(p2))m=-1;
printf("To get from %s to %s takes %d knight moves.\n",a,b,m);
}
return 0;
}