HDU 1372 (搜索方向稍有改变) Knight Moves

其实手写模拟一个队列也挺简单的，尤其是熟练以后。

尼玛，这题欺负我不懂国际象棋，后来百度了下，国际象棋里骑士的走法就是中国象棋里面的马

所以搜索就有八个方向

对了注意初始化标记数组的时候，不要把起点标记为已走过。

因为测试数据里面有一组 f6 f6，此时样例输出的是0

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 struct Point

 {

     int x, y;

     int steps;

 }start, end, qu[];

 int vis[][];

 int dir[][] = {{, }, {-, }, {, -}, {-, -}, {, }, {-, }, {, -}, {-, -}};

 char col1, col2;

 int row1, row2;

 int head, tail;

 bool islegal(int x, int y)

 {

     return (x>= && x< && y>= && y< && (!vis[x][y]));

 }

 void BFS(void)

 {

     head = , tail = ;

     qu[].x = start.x;

     qu[].y = start.y;

     qu[].steps = ;

     while(head < tail)

     {

         if(qu[head].x == end.x && qu[head].y == end.y)

         {

             printf("To get from %c%d to %c%d takes %d knight moves.\n", col1, row1, col2, row2, qu[head].steps);

             return;

         }

         for(int i = ; i < ; ++i)

         {

             int xx = qu[head].x + dir[i][];

             int yy = qu[head].y + dir[i][];

             if(islegal(xx, yy))

             {

                 qu[tail].x = xx;

                 qu[tail].y = yy;

                 qu[tail++].steps = qu[head].steps + ;

                 vis[xx][yy] = ;

             }

         }

         ++head;

     }

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("1372in.txt", "r", stdin);

     #endif

     while(cin >> col1 >> row1 >> col2 >> row2)

     {

         start.x = row1 - , start.y = col1 - 'a';

         end.x = row2 - , end.y = col2 - 'a';

         memset(vis, , sizeof(vis));

         BFS();

     }

     return ;

 }

代码君