https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=380
做了这道题之后对BFS总算是有了点认识了。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int map[10][10]; 6 typedef struct node 7 { 8 int x, y, z; 9 node(int a, int b, int c) { x = a; y = b; z = c; } 10 node() {} 11 }queue; 12 13 queue q[100]; 14 15 int d[8][2] = { { 2, 1 }, { 2, -1 }, { -2, -1 }, { -2, 1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } }; 16 int bfs(int x1, int y1, int x2, int y2) 17 { 18 int move = 0, number = 1; 19 if (x1 == x2 && y1 == y2) return 0; 20 memset(map, 0, sizeof(map)); 21 q[0] = node(x1, y1, 0); 22 while (move < number) 23 { 24 queue p = q[move++]; 25 for (int k = 0; k < 8; k++) 26 { 27 int xx = p.x + d[k][0]; 28 int yy= p.y + d[k][1]; 29 if (xx == x2 && yy == y2) return p.z + 1; 30 if (!map[xx][yy] && xx>0 && xx<9 && yy>0 && yy < 9) 31 { 32 map[xx][yy] = 1; 33 q[number++] = node(xx, yy, p.z + 1); 34 } 35 } 36 } 37 } 38 39 int main() 40 { 41 char s1, s2; 42 int x1, x2, y1, y2; 43 while (cin >> s1 >> y1 >> s2 >> y2) 44 { 45 x1 = (int)(s1 - 'a' + 1); 46 x2 = (int)(s2 - 'a' + 1); 47 int x=bfs(x1, y1, x2, y2); 48 cout << "To get from "<<s1<<y1<< " to " <<s2<<y2<< " takes "<<x <<" knight moves."<< endl; 49 } 50 return 0; 51 }