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 }