1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5  6 struct Point { 7     char r, c; 8     Point(char r = ‘ ‘, char c = ‘ ‘): r(r), c(c) {}; 9 };10 11 int vis[60][110], d[60][110];12 13 const int dir[8][2] = {14                     {2, -1}, {1, -2},15                     {-1, -2}, {-2, -1},16                     {-2, 1}, {-1, 2},17                     {1, 2}, {2, 1} };18 int main() {19     char s[3], t[3];20     while (scanf("%s%s", s, t) == 2) {21         memset(vis, 0, sizeof(vis));22         Point p; p.r = s[1]; p.c = s[0];23         d[p.r][p.c] = 0;24         queue<Point> q;25         q.push(p);26         while (!q.empty()) {27             Point u = q.front(); q.pop();28             if (u.r == t[1] && u.c == t[0]) break;29             if (vis[u.r][u.c]) continue; else vis[u.r][u.c] = 1;30             for (int i = 0; i < 8; i++) {31                 char nr = u.r + dir[i][0], nc = u.c + dir[i][1];32                 if (nr >= ‘1‘ && nr <= ‘8‘ && nc >= ‘a‘ && nc <= ‘h‘) {33                     d[nr][nc] = d[u.r][u.c] + 1;34                     q.push(Point(nr, nc));35                 }36             }37         }38         printf("To get from %s to %s takes %d knight moves.\n", s, t, d[t[1]][t[0]]);39     }40     return 0;41 }