简答的BFS

求“马”从一点到另一点的最短距离，马走日，BFS即可

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define Max 0x7f7f7f7f 5 using namespace std; 6  7 int visited[10][10]; 8 int ans[10][10]; 9 char a[5],b[5];10 int dir[9][2]={
   {-2,1},{-2,-1},{
   2,1},{
   2,-1},{-1,2},{-1,-2},{
   1,2},{
   1,-2}};11 struct node12 {13     int x;14     int y;15 };16 node path[100];17 void bfs(int x1,int y1,int x2,int y2)18 {19     memset(visited,0,sizeof(visited));20     memset(ans,Max,sizeof(ans));21     int head=0;22     int tail=1;23     path[head].x=x1;24     path[head].y=y1;25     ans[x1][y1]=0;26     visited[x1][y1]=1;27     while(head
        
         =0 && xx<8 && yy>=1&& yy<=8 )40             {41                 ans[xx][yy]=ans[x][y]+1;42                 visited[xx][yy]=1;43                 path[tail].x=xx;44                 path[tail].y=yy;45                 tail++;            }46         }47         head++;48     }49 }50 int main()51 {52     while(scanf("%s %s",a,b)!=EOF)53     {54         int x1=a[0]-'a';55         int y1=a[1]-'0';56         int x2=b[0]-'a';57         int y2=b[1]-'0';58         bfs(x1,y1,x2,y2);59         printf("To get from %s to %s takes %d knight moves.\n", a,b,ans[x2][y2]);60 61     }62     return 0;63 }
        
       
      
     

EN