e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6Sample Output
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求最短路，需要注意的是国际象棋中骑士和中国象棋中的马一样走日字
代码：
#include<iostream> #include<queue> #include<cstdio> using namespace std; const int N = 10; typedef struct { int x; int y; } P; int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1}; int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2}; int vis[N][N]; int d[N][N]; char s[5]; char e[5]; int sx, sy, ex, ey; int check(int x, int y) { return x >= 0 && x < 8 && y >= 0 && y < 8; } void bfs() { queue<P> que; P p; p.x = sx; p.y = sy; que.push(p); vis[sx][sy] = 1; while(que.size()) { P p = que.front(); que.pop(); int x = p.x; int y = p.y; if(x == ex && y == ey) { printf("To get from %s to %s takes %d knight moves.\n", s, e, d[x][y]); break; } for(int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if(check(nx, ny) && !vis[nx][ny]) { vis[nx][ny] = 1; d[nx][ny] = d[x][y] + 1; P p; p.x = nx; p.y = ny; que.push(p); } } } } int main() { while(cin >> s >> e) { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) d[i][j] = vis[i][j] = 0; } sx = s[1] - ‘0‘ - 1; sy = s[0] - ‘a‘; ex = e[1] - ‘0‘ - 1; ey = e[0] - ‘a‘; bfs(); } return 0; }
原文：https://www.cnblogs.com/kindleheart/p/9297373.html