本文共 1380 字，大约阅读时间需要 4 分钟。

13381

56.27%

5157

93.21%

题目类型： 搜索

样例输入：

e2 e4a1 b2b2 c3a1 h8a1 h7h8 a1b1 c3f6 f6

样例输出：

To get from e2 to e4 takes 2 knight moves.To get from a1 to b2 takes 4 knight moves.To get from b2 to c3 takes 2 knight moves.To get from a1 to h8 takes 6 knight moves.To get from a1 to h7 takes 5 knight moves.To get from h8 to a1 takes 6 knight moves.To get from b1 to c3 takes 1 knight moves.To get from f6 to f6 takes 0 knight moves.

分析：

这题也是一道十分经典的搜索入门题。  由于题目是指定象棋中马的开始位置，与目标位置， 要求马以最少的步数走到目标位置。 凡是求最短步数的，一般用BFS做比较好。

求步数时， 有个小技巧， 开个vis数组，初始化为0， 然后这个用来记录走的步数，而不仅仅是用来标记是否走过。具体见代码

#include
   
    #include
    
     #include
     
      using namespace std;char start[3], end[3];int dir[8][2] = {
  {-2,1},{-1,2},{1,2},{2,1},                 {2,-1},{1,-2},{-1,-2},{-2,-1}};int vis[10][10]; struct Node{int x, y; };Node que[1000];void bfs(){    int front=0, rear=1;    que[0].x=start[0]-'a', que[0].y=start[1]-'0'-1;    vis[que[0].x][que[0].y] = 1;    while(front
      
       =0 && dx<8 && dy>=0 && dy<8 && !vis[dx][dy]){                vis[dx][dy] = vis[t.x][t.y]+1;  // 记住步数                Node temp;                temp.x=dx, temp.y=dy;                que[rear++] = temp;            }        }    }}int main(){#ifdef LOCAL    freopen("input.txt", "r", stdin);#endif    while(~scanf("%s %s", start, end) && start[0]){        memset(vis, 0, sizeof(vis));        bfs();    }    return 0;}
      
     
    
   

转载地址：http://kyzni.baihongyu.com/