八数码难题——BFS

原题链接：https://www.acwing.com/problem/content/847/

通常情况下很难看出这是一道BFS题

或者说看不出怎么表示状态，毕竟它的状态涉及到整个矩阵

但是可以用一种unordered_map

其内部结构为哈希表，查找速度极其高效，但是建立比较费时

因此涉及到查找问题时可以考虑unordered_map

unordered_map <type a,type b> 变量名

定义它时需要两个变量类型，a为下标，b为值

因此我们甚至可以用一个字符串来当下标

解决了状态表示问题，那么此map的值就可以是达到这个状态需要移动的步数

而unordered_map的其中一个成员函数count（下标）则可以查找对应哈希值中有几个元素

在此题中可以表示对应状态是否被遍历过

若元素个数为0则没有遍历过，否则则遍历过，没有必要重复遍历

auto则是一个占位符，定义变量时可以根据被定义变量所覆的值自动推测该变量变量类型

也就是说定义auto类型的变量时必须初始化

string函数中有一个查找函数，find（要查找的字符），结果会返回这个字符第一次出现所在下标

最后满分代码呈上

 1 #include <bits/stdc++.h>
 2 #include <string>
 3 #include <queue>
 4 #include <unordered_map>
 5 using namespace std;
 6 string s;
 7 queue <string> q;
 8 unordered_map <string,int> d;
 9 int mx[4]={0,1,0,-1},my[4]={1,0,-1,0};
10 int bfs(){
11     q.push(s);
12     d[s]=0;
13     while(q.size()){
14         auto t=q.front(); 
15         //auto 根据后面的赋值自动判断变量类型 
16         int dis=d[t];
17         q.pop();
18         if(t=="12345678x")return dis;
19         int wz=t.find('x');
20         int px=wz/3,py=wz%3;
21         for(int i=0;i<4;i++){
22             int nx=px+mx[i];
23             int ny=py+my[i];
24             if(nx>=0&&ny>=0&&nx<3&&ny<3){
25                 swap(t[wz],t[nx*3+ny]);
26                 if(!d.count(t)){
27                     //这个放在判断越界的总条件里会出错
28                     //应该输出19时输出-1 
29                     q.push(t);
30                     d[t]=dis+1;
31                 }
32                 swap(t[wz],t[nx*3+ny]);
33             }
34         }
35     }
36     return -1;
37 }
38 int main(){
39     for(int i=0;i<9;i++){
40         char c;
41         cin>>c;
42         s+=c;
43     }
44     cout<<bfs();
45     return 0;
46 }