4.八数码 BFS

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 //用哈希表来存所有距离
 4 int bfs(string start) {
 5     string end = "12345678x"; //终止状态
 6     queue<string> q; //宽搜的队列
 7     unordered_map<string, int> d; //宽搜的数组
 8     q.push(start);
 9     d[start] = 0; //起点到起点的距离是零
10     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
11     while (q.size()) {
12         string t = q.front();
13         q.pop();
14         if (t == end) {
15             return d[t];
16         }
17         int distance = d[t];
18         //状态转移
19         int k = t.find('x'); //找到x的位置
20         int x = k / 3, y = k % 3; //找到在3 * 3方格中的位置
21         for (int i = 0; i < 4; i++) {
22             int a = x + dx[i], b = y + dy[i];
23             if (a >= 0 && a < 3 && b >= 0 && b < 3) {
24                 swap(t[k], t[3 * a + b]); //状态更新
25                 if (d.count(t) == 0) { //如果更新完之后的状态t没有被搜到的话
26                     q.push(t); //就找到了一个新的状态
27                     d[t] = distance + 1; //更新新的状态的距离
28                 }
29                 swap(t[k], t[3 * a + b]); //恢复状态
30             }
31         }
32     }
33     return -1;
34 }
35 int main() {
36     string start = ""; //初始状态
37     for (int i = 0; i < 9; i++) {
38         string c;
39         cin >> c;
40         start += c;
41     }
42     cout << bfs(start) << endl;
43     return 0;
44 }