嗯...

 

题目链接：

 

这是一道很典型的bfs，跟马走日字一个道理，然后用dir数组确定骑士可以走的几个方向，然后从起点到终点跑一遍最典型的bfs即可...注意HDU的坑爹输入和输出...

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 int ex, ey, sx, sy, step, g[10][10]; 9 10 struct node{11     int x, y, step;12 };13 14 int dir[8][2] = {
    {
    2, 1}, {
    1, 2}, {-1, 2}, {
    2, -1}, {-2, 1}, {
    1, -2}, {-1, -2}, {-2, -1}};15 //方向 16 inline void bfs(){17     memset(g, 0, sizeof(g));18     queue
          
            q;19     node now, next;20     now.x = sx;21     now.y = sy;22     now.step = 0;23     g[now.x][now.y] = 1;24     q.push(now);25     while(!q.empty()){26         now = q.front();27         q.pop();28         if(now.x == ex && now.y == ey){29             step = now.step;30             return;//找到终点 31         }32         for(int i = 0; i < 8; i++){33             next.x = now.x + dir[i][0];34             next.y = now.y + dir[i][1];35             if(next.x >= 1 && next.x <= 8 && next.y >= 1 && next.y <= 8 && !g[next.x][next.y]){36                 next.step = now.step + 1;37                 g[next.x][next.y] = 1;38                 q.push(next);39             }40         }41     }42 }43 44 45 int main(){46     char c1, c2;47     int s, t;48     while(~scanf("%c%d %c%d", &c1, &s, &c2, &t)){49         getchar();50         sx = c1 - 'a' + 1;51         sy = s;52         ex = c2 - 'a' + 1;53         ey = t;//起终点 54         bfs();55         printf("To get from %c%d to %c%d takes %d knight moves.\n", c1, s, c2, t, step);56     }57     return 0;58 }