题目

样例全过

代码：

#include <bits/stdc++.h>
using namespace std;
bool vis[10][10];

int dx[8]={1,2,2,1,-1,-2,-2,-1};
int dy[8]={2,1,-1,-2,-2,-1,1,2};
char a[10],b[10];
struct State{
	int x;
	int y;
	int step;
};
int bfs(State s,State en){
	State now,next;
	s.step=0;
	vis[s.x][s.y]=1;
	queue<State> q;
	q.push(s);
	while(!q.empty()){
		now=q.front();
		if(now.x==en.x&&now.y==en.y) return now.step;
		for(int i=0;i<8;i++){
			next.x=now.x+dx[i];
			next.y=now.y+dy[i];
			if(next.x>=1&&next.x<=8&&next.y>=1&&next.y<=8&&vis[next.x][next.y]==0){
				next.step=now.step+1;
				q.push(next);
				vis[next.x][next.y]=1;
			}
		}
		q.pop();
	}
	return 0;
}
int main(){
	
	while(scanf("%s%s",&a,&b)!=EOF){
		State t1,t2;
		t1.x=a[0]-'a'+1;
		t1.y=a[1]-'0';
		t2.x=b[0]-'a'+1;
		t2.y=b[1]-'0';
		memset(vis,0,sizeof(vis));
		memset(a,'0',sizeof(a));
		int ans=bfs(t1,t2);
		printf("To get from %c%c to %c%c takes %d knight moves.\n",a[0],a[1],b[0],b[1],ans);
	}
	return 0;
}