问题链接：。基础级练习题，用C++语言编写程序。

题意简述：给出国际象棋棋盘中的两个点，求马从一个点跳到另一个点的最少步数。

问题分析：典型的BFS问题。在BFS搜索过程中，马跳过的点就不必再跳了，因为这次再跳下去不可能比上次步数少。

程序说明：程序中，使用了一个队列来存放中间节点，但是每次用完需要清空。

这里给出两个版本的程序，有一个是设置了边界的。

AC的C++语言程序如下：

/* UVA439 POJ2243 HDU1372 ZOJ1091 Knight Moves */#include 
    
     #include 
     
      #include 
      
       using namespace std;const int DIRECTSIZE = 8;struct direct {    int drow;    int dcol;} direct[DIRECTSIZE] =    {
   {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};const int MAXN = 8;char grid[MAXN][MAXN];struct node {    int row;    int col;    int level;};node start, end2;int ans;void bfs(){    queue
       
         q;    memset(grid, ' ', sizeof(grid));    grid[start.row][start.col] = '*';    ans = 0;    q.push(start);    while(!q.empty()) {        node front = q.front();        q.pop();        if(front.row == end2.row && front.col == end2.col) {            ans = front.level;            break;        }        for(int i=0; i
        
         > startc >> start.row >> endc >> end2.row) {        start.row--;        start.col = startc - 'a';        start.level = 0;        end2.row--;        end2.col = endc - 'a';        bfs();        printf("To get from %c%d to %c%d takes %d knight moves.\n", startc, start.row+1, endc, end2.row+1, ans);    }    return 0;}
        
       
      
     
    

另外一版AC的C++语言程序如下：

/* UVA439 POJ2243 HDU1372 ZOJ1091 Knight Moves */#include 
    
     #include 
     
      #include 
      
       using namespace std;#define MAXN 8#define DIRECTSIZE 8struct direct {    int drow;    int dcol;} direct[DIRECTSIZE] =    {
   {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};char grid[MAXN+4][MAXN+4];int startcol, startrow, endcol, endrow;int ans;struct node {    int row;    int col;    int level;};queue
       
         q;void bfs(){    ans = 0;    node start;    start.row = startrow;    start.col = startcol;    start.level = 0;    q.push(start);    while(!q.empty()) {        node front = q.front();        q.pop();        if(front.row == endrow && front.col == endcol) {            ans = front.level;            break;        }        for(int i=0; i