hdu1372 参考答案

   1 /*
   2 zju1091 hdu1372 经典：跳马问题
   3 ymc 2008/8/30
   4 题目大意：
   5 一只马在8×8的棋盘上从一个位置跳到另外一个位置所需要的最少步数。
   6 分析与解题思路：
   7 从起点开始BFS搜索。还可以简历一个图，任意两个点之间的最短路径。
   8 */
   9 #include <iostream>
  10 #include <queue>
  11 using namespace std;
  12 int sx,sy,ex,ey;
  13 int dist[8][8];
  14 int step[8][2]={{-1,2},{-1,-2},{1,2},{1,-2},\
  15                 {2,1},{2,-1},{-2,1},{-2,-1}};
  16 int BFS()
  17 {
  18     memset(dist,-1,sizeof(dist));
  19     queue<int> q;
  20     int x1,y1,x2,y2;
  21     dist[sx][sy]=0;
  22     q.push(sx);
  23     q.push(sy);
  24     while(!q.empty())
  25     {
  26         x1=q.front();q.pop();
  27         y1=q.front();q.pop();
  28         if(x1==ex&&y1==ey)
  29                 return dist[x1][y1];
  30         for(int i=0;i<8;i++)
  31         {
  32             x2=x1+step[i][0];
  33             y2=y1+step[i][1];
  34             if(x2<0||x2>7||y2<0||y2>7||dist[x2][y2]>0)
  35                 continue;
  36             dist[x2][y2]=dist[x1][y1]+1;
  37             q.push(x2);
  38             q.push(y2);
  39         }
  40     }
  41     return -1;
  42 }
  43 int main()
  44 {
  45     char a[3],b[3];
  46     int ans;
  47     while(scanf("%2s %2s",a,b)!=EOF)
  48     {
  49         sx=a[0]-'a';
  50         sy=a[1]-'1';
  51         ex=b[0]-'a';
  52         ey=b[1]-'1';
  53         ans=BFS();
  54         printf("To get from %s to %s takes %d knight moves.\n",a,b,ans);
  55     }
  56 }