bfs，用队列记录步数
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> using namespace std; #define DEBUG const int maxn=1000+5,maxv=26; int a,b,c,d; bool visited[maxn][maxn]; char s[maxn]; int qx[maxn],qy[maxn],qcnt[maxn],f,t,cnt; int mv[8][2]={1,2,2,1,2,-1,1,-2,-1,-2,-2,-1,-2,1,-1,2}; void bfs(){ qx[t]=a; qcnt[t]=0; qy[t++]=b; while(t>f){ int u=qx[f]; int tcnt=qcnt[f]; int v=qy[f++]; if(u<0||u>7||v<0||v>7)continue; if(visited[u][v])continue; // printf("%d-%d-%d\n", u,v,tcnt); visited[u][v]=1; if(u==c&&v==d)printf("To get from %c%c to %c%c takes %d knight moves.\n",a+'a',b+'1',c+'a',d+'1',tcnt); for(int i=0;i<8;i++){ qx[t]=u+mv[i][0]; qcnt[t]=tcnt+1; qy[t++]=v+mv[i][1]; } } } int main(){ #ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while(fgets(s,6,stdin)){ memset(visited,0,sizeof(visited)); memset(qx,0,sizeof(qx)); memset(qy,0,sizeof(qy)); memset(qcnt,0,sizeof(qcnt)); f=t=0; a=s[0]-'a'; b=s[1]-'1'; c=s[3]-'a'; d=s[4]-'1'; // cout<<s<<endl; // cout<<a<<b<<c<<d<<endl; bfs(); } #ifdef DEBUG fclose(stdin); fclose(stdout); #endif return 0; }