題目地址：1936. Knight Moves
思路：
這道題一開始不理解題意…orz...囧，看大神們理解的。
題意是說一個8*8的國際象棋，騎士以馬的形式走動（“日”字型），指定兩個點，輸出最小的步驟。
可以利用廣度搜索解決。
具體代碼如下：
1 #include <iostream>
2 #include <queue>
3 #include <cstring>
4 #include <string>
5 using namespace std;
6
7 int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; //可以走八個方向
8 int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
9
10 bool visited[100];
11
12 int main() {
13 int t;
14 cin >> t;
15 while (t--) {
16 memset(visited, false, sizeof(visited));
17 int distance[100] = {0};
18
19 string node1, node2;
20 cin >> node1 >> node2;
21
22 int X = (node1[0]-'a')*8 + node1[1]-'1';
23 int Y = (node2[0]-'a')*8 + node2[1]-'1';
24
25 queue<int> store;
26 store.push(X);
27 while (!store.empty()) {
28 if (store.front() == Y)
29 break;
30
31 int x = store.front()/8;
32 int y = store.front()%8;
33
34 for (int i = 0; i < 8; i++) {
35 int nx = x+dx[i];
36 int ny = y+dy[i];
37
38 if (nx < 0||nx > 7||ny < 0||ny > 7)
39 continue;
40 int temp = nx*8 + ny;
41
42 if (!visited[temp]) {
43 store.push(temp);
44 visited[temp] = true;
45 distance[temp] = distance[store.front()] + 1;
46 }
47 }
48 store.pop();
49 }
50 cout << "To get from " << node1
51 << " to " << node2 << " takes "
52 << distance[Y] << " knight moves.\n";
53 }
54
55 return 0;
56 }
57
