骑士巡游找最短路。
单向bfs：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 const int N = 8; 7 const int M = N * N; 8 int step[N][N]; 9 int dir[N][2] = { 1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1 }; 10 11 struct Node 12 { 13 int x, y; 14 15 Node () {} 16 17 Node ( int _x, int _y ) 18 { 19 x = _x, y = _y; 20 } 21 22 } q[M]; 23 24 bool ok( int x, int y ) 25 { 26 return x >= 0 && x < N && y >= 0 && y < N && step[x][y] == -1; 27 } 28 29 int bfs( char src[], char des[] ) 30 { 31 int sx = src[0] - 'a', sy = src[1] - '1'; 32 int ex = des[0] - 'a', ey = des[1] - '1'; 33 memset( step, -1, sizeof(step) ); 34 int head = 0, tail = 0; 35 q[tail++] = Node( sx, sy ); 36 step[sx][sy] = 0; 37 while ( head < tail ) 38 { 39 Node t = q[head++]; 40 if ( t.x == ex && t.y == ey ) return step[t.x][t.y]; 41 for ( int i = 0; i < N; i++ ) 42 { 43 int xx = t.x + dir[i][0]; 44 int yy = t.y + dir[i][1]; 45 if ( ok( xx, yy ) ) 46 { 47 q[tail++] = Node( xx, yy ); 48 step[xx][yy] = step[t.x][t.y] + 1; 49 } 50 } 51 } 52 return -1; 53 } 54 55 int main() 56 { 57 char s[3], t[3]; 58 while ( scanf("%s%s", s, t) != EOF ) 59 { 60 printf("To get from %s to %s takes %d knight moves. ", s, t, bfs( s, t )); 61 } 62 return 0; 63 }
双向bfs：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 7 const int INF = 9999999; 8 const int N = 8; 9 const int M = N * N; 10 int step[N][N]; 11 int visit[N][N]; 12 int dir[N][2] = { 1, 2, 1, -2, -1, 2, -1, -2, 2, 1, 2, -1, -2, 1, -2, -1 }; 13 14 struct Node 15 { 16 int x, y; 17 18 Node () {} 19 20 Node ( int _x, int _y ) 21 { 22 x = _x, y = _y; 23 } 24 25 }; 26 27 bool ok( int x, int y ) 28 { 29 return x >= 0 && x < N && y >= 0 && y < N; 30 } 31 32 queue<Node> q1, q2; 33 34 int bfs( char src[], char des[] ) 35 { 36 int sx = src[0] - 'a', sy = src[1] - '1'; 37 int ex = des[0] - 'a', ey = des[1] - '1'; 38 if ( sx == ex && sy == ey ) return 0; 39 while ( !q1.empty() ) q1.pop(); 40 while ( !q2.empty() ) q2.pop(); 41 memset( visit, 0, sizeof(visit) ); 42 q1.push( Node( sx, sy ) ); 43 visit[sx][sy] = 1; 44 step[sx][sy] = 0; 45 q2.push( Node( ex, ey ) ); 46 visit[ex][ey] = 2; 47 step[ex][ey] = 0; 48 int ans = INF, sp = 0; 49 while ( !q1.empty() && !q2.empty() ) 50 { 51 while ( !q1.empty() && step[q1.front().x][q1.front().y] == sp ) 52 { 53 Node tmp = q1.front(); q1.pop(); 54 for ( int i = 0; i < N; i++ ) 55 { 56 int xx = tmp.x + dir[i][0], yy = tmp.y + dir[i][1]; 57 if ( ok( xx, yy ) ) 58 { 59 if ( visit[xx][yy] == 1 ) continue; 60 if ( visit[xx][yy] == 2 ) 61 { 62 ans = min( ans, step[tmp.x][tmp.y] + step[xx][yy] + 1 ); 63 continue; 64 } 65 q1.push( Node( xx, yy ) ); 66 step[xx][yy] = step[tmp.x][tmp.y] + 1; 67 visit[xx][yy] = 1; 68 } 69 } 70 } 71 while ( !q2.empty() && step[q2.front().x][q2.front().y] == sp ) 72 { 73 Node tmp = q2.front(); q2.pop(); 74 for ( int i = 0; i < N; i++ ) 75 { 76 int xx = tmp.x + dir[i][0], yy = tmp.y + dir[i][1]; 77 if ( ok( xx, yy ) ) 78 { 79 if ( visit[xx][yy] == 2 ) continue; 80 if ( visit[xx][yy] == 1 ) 81 { 82 ans = min( ans, step[tmp.x][tmp.y] + step[xx][yy] + 1 ); 83 continue; 84 } 85 q2.push( Node( xx, yy ) ); 86 step[xx][yy] = step[tmp.x][tmp.y] + 1; 87 visit[xx][yy] = 2; 88 } 89 } 90 } 91 sp++; 92 if ( ans != INF ) return ans; 93 } 94 return -1; 95 } 96 97 int main() 98 { 99 char s[3], t[3]; 100 while ( scanf("%s%s", s, t) != EOF ) 101 { 102 printf("To get from %s to %s takes %d knight moves. ", s, t, bfs( s, t )); 103 } 104 return 0; 105 }