今天兴致再起，突发想法，用第三种方法，广度优遍历棋盘，每走一步，就在那个位记录下到达那个位置所需的步数，AC此题。
#include <iostream>
#include <queue>
#include <string.h>using namespace std;typedef struct Tdata //定义结点数据类型
{int x;int y;
}data;data end; //目标结点int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1}; //行偏移量
int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2}; //列偏移量int vis[10][10]; //步数数组，初始化为-1，既记录步数，又标记状态void bfs(data n) //广度优先遍历，记录走到各个位置的所需步数
{int i;queue<data> qu; //广度优先中用来的队列qu.push(n); //第一个结点入列vis[n.x][n.y] = 0; //走过了，将此结点的步数标记为1data newnode;while(!qu.empty()){n = qu.front();qu.pop();for(i = 0; i < 8; i++) //分别向8个方向进行遍历{newnode.x = n.x + dx[i];newnode.y = n.y + dy[i];if(vis[newnode.x][newnode.y] == -1 && newnode.x >= 0 && newnode.x < 8 && newnode.y >= 0 && newnode.y < 8) //可走入的条件：没走过，不出界{qu.push(newnode);vis[newnode.x][newnode.y] = vis[n.x][n.y] + 1; //记录走到这里的步数}}}
}int main()
{string a, b;data begin; //起始位置while(cin>>a>>b){memset(vis, -1, 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;bfs(begin);cout<<"To get from "<<a<<" to "<<b<<" takes "<<vis[end.x][end.y]<<" knight moves."<<endl;}return 0;
}