AcWing 845.八数码
2022-09-06 22:46:00

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int bfs(string start)
 5 {
 6     queue<string> q;
 7     unordered_map<string, int> d;
 8     string end = "12345678x";
 9     int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
10 
11     q.push(start);
12     d[start] = 0;//初始化最初x的距离
13     while(q.size())
14     {
15         auto t = q.front();
16         q.pop();
17         //记录当前距离，如果是最终状态则返回距离
18         int dis = d[t];
19         if(t == end) return dis;
20         //查询x在字符串中的下标，然后返回x在数组中的下标
21         int k = t.find('x');//find返回'x'的下标（从0开始）
22         int x = k/3, y = k%3;
23 
24         for(int i=0; i<4; i++)
25         {
26             //求转移后x的下标
27             int a = x+dx[i], b = y+dy[i];
28             //如果当前状态没有越界
29             if(a >= 0 && a < 3 && b >= 0 && b < 3)
30             {
31                 //转换x
32                 swap(t[k], t[a*3+b]);
33                 //如果当前状态是第一次遍历，则入队
34                 if(!d.count(t))//count返回t的个数
35                 {
36                     q.push(t);
37                     d[t] = dis + 1;//更新距离数组
38                 }
39                 //还原状态
40                 swap(t[k], t[a*3+b]);
41             }
42         }
43     }
44     return -1;
45 }
46 
47 int main()
48 {
49     string c, start;
50     for(int i=0; i<9; i++)
51     {
52         cin >> c;
53         start += c;
54     }
55     cout << bfs(start) << endl;
56     return 0;
57 }