| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 14114 | Accepted: 7870 |
Description
Input
Output
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.
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
int x;
int y;
int step;
}q,end,w;
int vis[10][10];
char x,y;
int a,b;
int u[][2]={-2,-1,-1,-2,1,-2,2,-1,2,1,1,2,-1,2,-2,1};
int sum,c,d;
queue<node>s;
void bfs(int x,int y)
{
end.x=d;
end.y=c;
q.x=x;
q.y=y;
q.step=0;
queue<node>s;
while(!s.empty())s.pop();
s.push(q);
while(!s.empty())
{
q=s.front();
s.pop();
if(q.x==end.x&&q.y==end.y)
{
printf("To get from %c%d to %c%d takes %d knight moves.\n",a-1+‘a‘,b,c-1+‘a‘,d,q.step);
return;
}
for(int i=0;i<8;i++)
{
w.x=q.x+u[i][0];
w.y=q.y+u[i][1];
w.step=q.step+1;
if(w.x>0&&w.x<9&&w.y>0&&w.y<9&&vis[w.x][w.y]==0)
{
s.push(w);
vis[w.x][w.y]=1;
}
}
}
}
int main()
{
while(cin>>x>>b>>y>>d)
{
memset(vis,0,sizeof(vis));
a=x-‘a‘+1;
c=y-‘a‘+1;
bfs(b,a);
}
}
原文：http://www.cnblogs.com/--lr/p/7073676.html