#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<vector> #include<queue> #include<map> #include<algorithm> #include<set> #define scnaf scanf #define cahr char #define bug puts("bugbugbug"); using namespace std; typedef long long ll; typedef pair<int,int> pii; bool pd(int x,int y)//判断点是否在棋盘上 { if(x>=1&&x<=8&&y>=1&&y<=8) return 1; return 0; } const int mod=1000000007; const int maxn=1e5+5; const int inf=1e9; char a[10],b[10]; int fx[8][2]={1,2, 1,-2, -1,2, -1,-2, 2,1, 2,-1, -2,1, -2,-1}; struct T { int x,y,cnt; }; queue<T>q; bool visit[10][10]; int main() { while(~scanf("%s%s",a,b)) { while(!q.empty())q.pop(); memset(visit,0,sizeof(visit)); int x1=a[0]-'a'+1; int y1=a[1]-'0'; int x2=b[0]-'a'+1; int y2=b[1]-'0'; q.push((T){x1,y1,0}); while(!q.empty()) { T now=q.front(); q.pop(); if(now.x==x2&&now.y==y2){ printf("To get from %s to %s takes %d knight moves.\n",a,b,now.cnt); break; } for(int i=0;i<8;i++) { T next; next.cnt=now.cnt+1; next.x=now.x+fx[i][0]; next.y=now.y+fx[i][1]; if(pd(next.x,next.y)&&visit[next.x][next.y]==0){ visit[next.x][next.y]=1; q.push(next); } } } } } |
Double click to view unformatted code.