简单骑士周游问题，BFS，有障碍物，（可能存在无障碍物的情况），起点和终点不会相同，起点终点无障碍物
若能从起点出发到终点则输出步数，否者输入不能到达
#include#include #include #define N 70using namespace std;bool g[N][N];int b;int start,end;struct node{ int n,r,c,k;};queue q;int BFS(){ int ans,i,k,R[10],C[10],FIND; struct node tmp; while(!q.empty()) q.pop(); tmp.n=start; tmp.r=(start%8)==0 ? start/8 : start/8+1; tmp.c=(start%8)==0 ? 8: start%8; tmp.k=0; q.push(tmp); FIND=0; while(!q.empty()) { tmp=q.front(); k=tmp.k; q.pop(); R[1]=tmp.r-2; C[1]=tmp.c-1; R[2]=tmp.r-2; C[2]=tmp.c+1; R[3]=tmp.r-1; C[3]=tmp.c+2; R[4]=tmp.r+1; C[4]=tmp.c+2; R[5]=tmp.r+2; C[5]=tmp.c+1; R[6]=tmp.r+2; C[6]=tmp.c-1; R[7]=tmp.r+1; C[7]=tmp.c-2; R[8]=tmp.r-1; C[8]=tmp.c-2; for(i=1; i<=8; i++) { if(R[i]>=1 && R[i]<=8 && C[i]>=1 && C[i]<=8 && !g[R[i]][C[i]]) { tmp.n=(R[i]-1)*8+C[i]; tmp.r=R[i]; tmp.c=C[i]; tmp.k=k+1; q.push(tmp); if(tmp.n==end) break; } } if(i<=8) {FIND=1; ans=tmp.k; break;} } return FIND==1 ? ans : -1; }int main(){ int i,j,r,c,T=0,ans; char s1[5],s2[5]; while(scanf("%d",&b)!=EOF && b!=-1) { T++; memset(g,0,sizeof(g)); for(i=1; i<=b; i++) { scanf("%s",s1); //读入全部的障碍物并在图上标记 c=s1[0]-'a'+1; r=s1[1]-'0'; g[r][c]=1; } scanf("%s",s1); scanf("%s",s2); c=s1[0]-'a'+1; r=s1[1]-'0'; start=(r-1)*8+c; c=s2[0]-'a'+1; r=s2[1]-'0'; end=(r-1)*8+c;/* for(i=1; i<=8; i++) { for(j=1; j<=8; j++) printf("%d ",g[i][j]); printf("\n"); } printf("start=%d end=%d\n",start,end);*/ ans=BFS(); if(ans==-1) printf("Board %d:not reachable\n",T); else printf("Board %d:%d moves\n",T,ans); } return 0;}