这个问题的难处，对我而言在于计步数，开始时想在for(i = 0; i < 8; i++)后来个cnt++计步数，事实证明，那是错误的，因为这样的话每一层的每个元素自己往8个方向移动后，都有个cnt++，而我们每层只应使cnt自加一次就够，于是，将每层最右边的结点保存下来，判断是每层的最右结点再加1。另一个问题是队列的清零问题，没的话，上一组测试数据将影响下一组测试数据。
#include <iostream>
#include <string.h>
#include <queue>using namespace std;typedef struct Tdata //定义结点数据类型
{int x;int y;
}data;int s[8][8]; //结点表：a1 对应 s[0][0]，a8 对应 s[0][7]
int vis[8][8]; //状态标记，0为未访问过，1为访问过
int cnt; //步数计数器int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; //与dy一起组成移动间距
int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2}; //与dx一起组成移动间距queue<data> qu; //广度优先遍历中用的队列int bfs(data a, data b) //a为起始点，b为目标点
{int i;if(a.x == b.x && a.y == b.y) //如果起始点已是目标点，返回步数return cnt;vis[a.x][a.y] = 1; //将起始点标记为已访问qu.push(a); //入列data rear = a, right; //rear为应该使步数+1时，正在遍历的结点， right用来保存每层遍历最右边的结点while(!qu.empty()){data temp = qu.front(); //取队头元素qu.pop(); //出列for(i = 0; i < 8; i++) //对8个方向进行遍历{data newnode; //朝某个方向去时的新结点newnode.x = temp.x + dx[i];newnode.y = temp.y + dy[i];if(newnode.x == b.x && newnode.y == b.y) //若已到达目标结点，返回步数return cnt+1;//否则，判断移动有没有出界，是否已经遍历过if(newnode.x >= 0 && newnode.x < 8 && newnode.y >= 0 && newnode.y < 8 && vis[newnode.x][newnode.y] == 0){qu.push(newnode); //入列right = newnode; //保存结点，只为了最后的每层最右边的那个点vis[newnode.x][newnode.y] = 1; //修改其访问状态}}if(temp.x == rear.x && temp.y == rear.y) //当正在访问的结点是所在层的最右结点时，步数+1{cnt++;rear = right; //将新一层的最右结点存起来}}return -1; //无法到达目标结点时，返回-1，虽然这种情况不会出现
}int main()
{string a, b;data begin, end;while(cin>>a>>b){memset(vis, 0, sizeof(vis)); //令状态数组的初始值为0，即未访问过begin.x = a[0] - 'a'; //转换begin.y = a[1] - '0' - 1;end.x = b[0] - 'a';end.y = b[1] - '0' - 1;cnt = 0; //步数清零cout<<"To get from "<<a<<" to "<<b<<" takes "<<bfs(begin, end)<<" knight moves."<<endl;while(!qu.empty()) //队列清空，这一步很重要，否则可能会使上次在qu中遗留下来的结点干扰现在的结果{qu.pop();}}return 0;
}