BFS可以想成树的层序遍历，关键是1)判重，表示偷懒用set判重;
2)判断搜索到第几层，用front表示当前层数，rear表示上一层层数。
#include<iostream>
#include<cstring>
#include<set>
#include<cstdio>
#include<queue>
#include<cctype>
using namespace std;
set<string> st;
char s1[5],s2[5];
const int dx[]={2,1,-1,-2,-2,-1, 1, 2};
const int dy[]={1,2, 2, 1,-1,-2,-2,-1};
int d[10000];
bool inside(char x,char y)
{return x>='a'&&x<='h'&&y>='1'&&y<='8';
}
bool check(char* A)
{string s=A; //直接st.count(A)会RunTime Error不知道为什么if(st.count(s)) return false;st.insert(s);return true;
}
int bfs()
{queue<char*> p;p.push(s1);int cnt=0;memset(d,0,sizeof(d));int front=1,rear=0;while(!p.empty()){char *p1=p.front();p.pop();if(!strcmp(p1,s2)) return rear;for(int i=0;i<8;i++){char* p2=new char[5];p2[0]=p1[0]+dx[i];p2[1]=p1[1]+dy[i];p2[2]='\0'; //一定要加if(inside(p2[0],p2[1])&&check(p2)){d[front++]=d[rear]+1;p.push(p2);}}rear++; //进入下一层}return -1;
}
int main()
{while(scanf("%s",s1)!=EOF&&scanf("%s",s2)){st.clear();printf("To get from %s to %s takes %d knight moves.\n",s1,s2,d[bfs()]);}return 0;
}