直接搜索加剪枝
剪枝可以考虑Cantor 展开，也可以直接用map1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
const int N=5,ed=12345678;
struct node {LL s;int k;};
map<LL,LL> M;
int ans=-1,w[N<<2];
queue<node> Q;
LL modify(LL s,int f)
{
for(int i=9;i>0;i--) w[i]=s%10,s/=10;
if (f)
{
int num=w[6];LL ret=0;
w[6]=w[5],w[5]=w[4],w[4]=num;
for(int i=1;i<=9;i++) ret=ret*10+w[i];
return ret;
}
else
{
int num=w[1];LL ret=0;
w[1]=w[4],w[4]=w[7],w[7]=w[8];
w[8]=w[9],w[9]=w[6],w[6]=w[3];
w[3]=w[2],w[2]=num;
for(int i=1;i<=9;i++) ret=ret*10+w[i];
return ret;
}
}
void bfs(LL st)
{
M[st]=0,Q.push((node){st,0});
while (!Q.empty())
{
node x=Q.front();Q.pop();
if (x.s==ed) {ans=x.k;return;}
LL nxt=modify(x.s,0);
if (M.find(nxt)==M.end())
{
M[nxt]=x.s;
Q.push((node){nxt,x.k+1});
}
nxt=modify(x.s,1);
if (M.find(nxt)==M.end())
{
M[nxt]=x.s;
Q.push((node){nxt,x.k+1});
}
}
}
void dfs(LL s)
{
if (!s) return;
dfs(M[s]);
for(int i=9;i>0;i--) w[i]=s%10,s/=10;
for(int i=1;i<=9;i++) printf("%d%c",w[i],i%3?' ':'\n');
printf("\n");
}
int main()
{
LL num=0;
for(int i=1;i<=9;i++)
{
int x;
scanf("%d",&x);
num=num*10+x;
}
bfs(num);
if (ans==-1) {puts("UNSOLVABLE");return 0;}
printf("%d\n",ans),dfs(ed);
return 0;
}