八数码第四境界——暴力反向BFS+康托展开判重+打表+回溯记录路径

（请先看前面3重境界）

由于第三重境界要开一个vector来嵌套许多vector来记录路径，那绝对是开销很大。所以我们采用回溯记录路径。

思路：

原来我们是采用康托展开，比如求出12345678x在全排列的第几个（这里无疑是第一个），用来判断这种状态是否已经到达过了，这里就是vis[1]=1代表已经访问过，vis[1]=0代表未访问过。在每次访问以后都置为1。而现在我们这里不一样了。我们存放的是层数。我们这里想要的是路径吧？所以说这里指的就是在这条路径上的第几个，我们的做法就是在最后找到以后，根据这个第几个，来逐一找到上一个，直到找到终点。以前我们每种状态维护的是一个路径，我们这里只需要维护一个操作就可以了。只要我们能把每种状态的路径，和上一种状态的路径，想办法关联起来，就可以了。

用来找到关联的结构体：

}res[N]; 

now存放的就是当前的操作（上下左右），fa就是这条路径上上一个状态的操作在这个res数组中存放的地方。就比如说我现在是这个数组的第10个，我的操作是上，我的fa是7，就代表我上一个操作被存放在了7，我们不断去取即可。所以我们一旦让一个点入栈了，也同时会在这个数组的尾端添加一个。赋予他当前的操作是什么，以及这条路径上上一个操作所存放的位置。这个怎么得知呢？因为我们就是通过上一种状态得出下一种状态的，所以我们只需要在上一种状态得出下一种状态的过程中，把他上一种状态所在这个数组中的位置给他，交给他去维护了。所以我们可以得知，这个res数组，并不是有序的。什么意思呢？并不是说这个状态的操作在这里，下一个状态的操作在这个数组的下一个位置，而是通过fa来进行关联。

上个图：

此外，我们上面讲的康托展开，vis[某个节点对应的康托值] = 这个res集合中的某一位，再以此为依据就能回溯出之前的路径了。

讲了这么多理论，具体看看细化的实现。

if语句判断如果不是在最后一列，那就肯定就可以右移。

下一行，和右边那个数进行交换。

h.index指的是x在状态中的位置

res[cnt].now=4，4指代的是右移操作

res[cnt].fa=h.pos这个指的是你上一个状态所在这个res数组的位置赋给你当前状态去维护

h.pos=cnt这是你当前状态所在这个res数组的位置

cnt++你插入了一个数，自然要++，不然接下来还用不用了

最后如果这个位置没有访问过，那么这个状态在vis中的值，也被置为和你当前h.pos位置一样的值。为什么这里也要作文章，因为最后你输出的时候你肯定要根据所要求的结果在res中定位，那你定位的依据是什么？只能以序列通过求康托值得出在vis中的位置，再去取得这个值。

如果vis[t]!=-1，那么就是这种状态肯定是有的，而我们在这个里面存储了他在res中的位置，所以再通过fa一步步回推，得出了序列。

全部代码

1. #define N 512345  
2.   
3. char ss[10];  
4. struct node  
5. {  
6.     char str[10];  
7.     int pos;  
8.     int index;  
9. };  
10. struct res  
11. {  
12.     int now,fa;  
13. }res[N];  
14. int vis[N];  
15. int  fac[] = {1,1,2,6,24,120,720,5040,40320};  
16. int over,cnt;  
17. int ans[N];  
18. int KT(char ss[])  
19. {  
20.     int i, j, t, sum;  
21.     int s[10];  
22.     for(i=0;i<9;i++)  
23.     {  
24.         if(ss[i]=='x')  
25.             s[i]=0;  
26.         else  
27.             s[i]=ss[i]-'0';  
28.     }  
29.     sum = 0;  
30.     for (i=0; i<9; i++)  
31.     {  
32.         t = 0;  
33.         for (j=i+1; j<9; j++)  
34.             if (s[j] < s[i])  
35.                 t++;  
36.         sum += t*fac[9-i-1];  
37.     }  
38.     return sum+1;  
39. }  
40. bool bfs()  
41. {  
42.     char c;  
43.     queue<node> q;  
44.     while(!q.empty())q.pop();  
45.     over = KT(ss);  
46.     node g,h;  
47.     for(int i=0;i<8;i++)  
48.         g.str[i]=i+1+'0';  
49.     g.str[8]='x';g.str[9]='\0';  
50.     g.pos=0;g.index=8;  
51.     int t=KT(g.str);  
52.     vis[t] = 0;  
53.     q.push(g);  
54.     cnt=1;  
55.     while(!q.empty())  
56.     {  
57.         g=q.front();q.pop();  
58.         int t = KT(g.str);  
59.         h=g;  
60.         if((h.index+1)%3!=0)  
61.         {  
62.             c=h.str[h.index];h.str[h.index]=h.str[h.index+1];h.str[h.index+1]=c;  
63.             h.index++;  
64.             res[cnt].now=4;res[cnt].fa=h.pos;h.pos=cnt;cnt++;  
65.             int t=KT(h.str);  
66.             if(vis[t]==-1)  
67.             {  
68.                 vis[t]=cnt-1;  
69.                 q.push(h);  
70.             }  
71.         }  
72.         h=g;  
73.         if(h.index%3!=0)  
74.         {  
75.             c=h.str[h.index];h.str[h.index]=h.str[h.index-1];h.str[h.index-1]=c;  
76.             h.index--;  
77.             res[cnt].now=3;res[cnt].fa=h.pos;h.pos=cnt;cnt++;  
78.             int t=KT(h.str);  
79.             if(vis[t]==-1)  
80.             {  
81.                 vis[t]=cnt-1;  
82.                 q.push(h);  
83.             }  
84.         }  
85.         h=g;  
86.         if(h.index<6)  
87.         {  
88.             c=h.str[h.index];h.str[h.index]=h.str[h.index+3];h.str[h.index+3]=c;  
89.             h.index+=3;  
90.             res[cnt].now=2;res[cnt].fa=h.pos;h.pos=cnt;cnt++;  
91.             int t=KT(h.str);  
92.             if(vis[t]==-1)  
93.             {  
94.                 vis[t]=cnt-1;  
95.                 q.push(h);  
96.             }  
97.         }  
98.         h=g;  
99.         if(h.index>2)  
100.         {  
101.             c=h.str[h.index];h.str[h.index]=h.str[h.index-3];h.str[h.index-3]=c;  
102.             h.index-=3;  
103.             res[cnt].now=1;res[cnt].fa=h.pos;h.pos=cnt;cnt++;  
104.             int t=KT(h.str);  
105.             if(vis[t]==-1)  
106.             {  
107.                 vis[t]=cnt-1;  
108.                 q.push(h);  
109.             }  
110.         }  
111.     }  
112.     return false;  
113. }  
114. int main()  
115. {  
116.     int i,j,k,kk,t,x,y,z;  
117.     memset(vis,-1,sizeof(vis));  
118.     res[0].now=-1;  
119.     bfs();  
120.     while(scanf("%s",ss)!=EOF)  
121.     {  
122.         for(i=1;i<9;i++)  
123.             scanf("%s",ss+i);  
124.         t = KT(ss);  
125.         if(vis[t]!=-1)  
126.         {  
127.             t = vis[t];  
128.             while(res[t].now!=-1)  
129.             {  
130.                 if(res[t].now==1)printf("d");  
131.                 if(res[t].now==2)printf("u");  
132.                 if(res[t].now==3)printf("r");  
133.                 if(res[t].now==4)printf("l");  
134.                 t=res[t].fa;  
135.             }  
136.         }  
137.         else  
138.             printf("unsolvable");  
139.         printf("\n");  
140.     }  
141.     return 0;  
142. }