八数码第一境界——暴力反向BFS+存状态

这题首先会遇到一个问题：BFS无法实施

为什么会无法实施？

正常情况，x从队列中取出，8、6入队

8从队列中取出，x和8交换，7、5入队

这个时候下一个要出队列的是6，但是你x在8原来的位置，怎么实施交换？

所以队列中应该入的是状态，可能很抽象，但是下面的图不抽象。

我们还是看6要出队列的时候的情况，就是第三行第一个。我们发现他可以出队列了。出队列，向左移动的一个情况以及向右移动的一个情况被添加到队列底端。

如何存这个队列？

采用结构体。

1. struct node  
2. {  
3.     string str;  
4.     vector<int>res;  
5.     int index;  
6. };  
7. map<string,int> mp;  
8. vector<int>res;  

str一维数组，把二维数组降了一维。

vector用来存你历次的移动方向。

index用来存当前str中的x在哪个位置。

map用来判断当前这种状态我们是否已经走过了。

具体BFS的方法？

1. while(!q.empty())  
2.     {  
3.         g=q.front();q.pop();  
4.         if(g.str==ss)  
5.         {  
6.             res=g.res;  
7.             return true;  
8.         }  
9.         h=g;  
10.         if((h.index+1)%3!=0)  
11.         {  
12.             c=h.str[h.index];h.str[h.index]=h.str[h.index+1];h.str[h.index+1]=c;  
13.             h.index++;  
14.             h.res.push_back(4);  
15.             if(mp[h.str]==0)  
16.             {  
17.                 mp[h.str]=true;  
18.                 q.push(h);  
19.             }  
20.         }  

第三行，出队列。

接下来的if判断，用来判断是否当前这个状态和我们要求的一样，如果是，那代表已经找到了，返回true。

h=g，把当前队首元素给h，因为当前的队首元素后面还要用，这里仅仅是代表了他右移的可能性。

接下来if判断，如果他不是最后一列，我们进入这个if，而且不用想在不是最后一列的情况下我们是可以右移的。

和右边的数交换。

x所在string中的位置增加一位。

4存入操作，4代表的是右移。

如果这种状态的键取出来的值是0，那就代表这种状态以前没走过，可以入队列，并且把这个状态设置为已走过。

完毕。

接下来几个方向也是几乎一样的操作。

全部代码

1. char s[101];  
2. struct node  
3. {  
4.     string str;  
5.     vector<int>res;  
6.     int index;  
7. };  
8. map<string,int> mp;  
9. vector<int>res;  
10.   
11. bool bfs(string ss)  
12. {  
13.     char c;  
14.     queue<node> q;  
15.     while(!q.empty())q.pop();  
16.     node g,h;  
17.     g.str="12345678x";g.res.clear();g.index=8;  
18.     q.push(g);  
19.     while(!q.empty())  
20.     {  
21.         g=q.front();q.pop();  
22.         if(g.str==ss)  
23.         {  
24.             res=g.res;  
25.             return true;  
26.         }  
27.         h=g;  
28.         if((h.index+1)%3!=0)  
29.         {  
30.             c=h.str[h.index];h.str[h.index]=h.str[h.index+1];h.str[h.index+1]=c;  
31.             h.index++;  
32.             h.res.push_back(4);  
33.             if(mp[h.str]==0)  
34.             {  
35.                 mp[h.str]=true;  
36.                 q.push(h);  
37.             }  
38.         }  
39.         h=g;  
40.         if(h.index%3!=0)  
41.         {  
42.             c=h.str[h.index];h.str[h.index]=h.str[h.index-1];h.str[h.index-1]=c;  
43.             h.index--;  
44.             h.res.push_back(3);  
45.             if(!mp[h.str])  
46.             {  
47.                 mp[h.str]=true;  
48.                 q.push(h);  
49.             }  
50.         }  
51.         h=g;  
52.         if(h.index<6)  
53.         {  
54.             c=h.str[h.index];h.str[h.index]=h.str[h.index+3];h.str[h.index+3]=c;  
55.             h.index+=3;  
56.             h.res.push_back(2);  
57.             if(!mp[h.str])  
58.             {  
59.                 mp[h.str]=true;  
60.                 q.push(h);  
61.             }  
62.         }  
63.         h=g;  
64.         if(h.index>2)  
65.         {  
66.             c=h.str[h.index];h.str[h.index]=h.str[h.index-3];h.str[h.index-3]=c;  
67.             h.index-=3;  
68.             h.res.push_back(1);  
69.             if(!mp[h.str])  
70.             {  
71.                 mp[h.str]=true;  
72.                 q.push(h);  
73.             }  
74.         }  
75.     }  
76.     return false;  
77. }  
78. int main()  
79. {  
80.     int i,j,k,kk,t,x,y,z;  
81.     while(scanf("%s",s)!=EOF)  
82.     {  
83.         mp.clear();  
84.         for(i=1;i<9;i++)  
85.             scanf("%s",s+i);  
86.         string ss(s);  
87.         if(bfs(ss))  
88.             for(i=res.size()-1;i>=0;i--)  
89.             {  
90.                 if(res[i]==1)printf("d");  
91.                 if(res[i]==2)printf("u");  
92.                 if(res[i]==3)printf("r");  
93.                 if(res[i]==4)printf("l");  
94.             }  
95.         else  
96.             printf("unsolvable");  
97.         printf("\n");  
98.     }  
99.     return 0;  
100. }