【LOJ#10027】魔板

本来想用双向广搜的,但是不太好保存路径,所以我就用的普通的bfs

思路很简单,从初始状态直接搜,每次扩展三个状态,用函数模拟一下三种变换,用map存储路径即可(拒绝康托展开,拒绝哈希,拒绝状压)

不得不说,对于数据不是很毒瘤的题,STL是真的好用啊……

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <map>
 6 #include <string>
 7 using namespace std;
 8 queue<string> q;
 9 string s;
10 map<string,string> dis;
11 void turna(string neww) {
12     string now=neww;
13     neww[0]=now[7];
14     neww[1]=now[6];
15     neww[2]=now[5];
16     neww[3]=now[4];
17     neww[7]=now[0];
18     neww[6]=now[1];
19     neww[5]=now[2];
20     neww[4]=now[3];
21     if(dis.count(neww)==0) {
22         q.push(neww);
23         dis[neww]=dis[now]+'A';
24     }
25 }
26 void turnb(string neww) {
27     string now=neww;
28     neww[0]=now[3];
29     neww[1]=now[0];
30     neww[2]=now[1];
31     neww[3]=now[2];
32     neww[7]=now[4];
33     neww[6]=now[7];
34     neww[5]=now[6];
35     neww[4]=now[5];
36     if(dis.count(neww)==0) {
37         q.push(neww);
38         dis[neww]=dis[now]+'B';
39     }
40 }
41 void turnc(string neww) {
42     string now=neww;
43     neww[1]=now[6];
44     neww[2]=now[1];
45     neww[6]=now[5];
46     neww[5]=now[2];
47     if(dis.count(neww)==0) {
48         q.push(neww);
49         dis[neww]=dis[now]+'C';
50     }
51 }
52 int main() {
53     q.push("12345678");
54     dis["12345678"]="";
55     for(int i=1,x;i<=8;i++) {
56         cin>>x;
57         s+=x+'0';
58     }
59     if(s=="12345678") {
60         printf("0");
61         return 0;
62     }
63     while(!q.empty()) {
64         turna(q.front());
65         turnb(q.front());
66         turnc(q.front());
67         q.pop();
68         if(dis.count(s)) {
69             cout<<dis[s].size()<<endl<<dis[s];
70             return 0;
71         }
72     }
73     return 0;
74 }
AC Code
原文地址:https://www.cnblogs.com/shl-blog/p/10628726.html