poj 2965

本题要结合poj 1753 来看最好。。。又有了一点搜索的经验。。加油。。。
 1 #include <iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 int step[655350];
 6 bool flag[655350];
 7 unsigned qState[655350];
 8 struct node{
 9     int from,index;
10 } f[655350];//用于存它在队列中的生成他的那个节点的位置，和生成他的那个节点的在位置数组中的位置即--i---也就是index；
11 int rear = 0,top = 0;
12 void init(){
13     char c;
14     int temp = 0;
15     memset(f,-1,sizeof(f));
16     for(int i=0;i<4;i++)
17     for(int j=0;j<4;j++){
18         cin>>c;
19         if(c=='-'){
20             temp |=(1<<(i*4+j));
21         }
22     }
23     qState[rear++] = temp;
24     flag[temp]=true;
25 }
26 int mve(int state,int i){
27     int temp = 0;
28     temp |= (1<<i);
29     int x = i/4;
30     int y  = i%4;
31     for(int k=0;k<4;k++)//所在的一行和一列都变
32         temp |= 1<<(x*4+k);
33     for(int k=0;k<4;k++)
34         temp |= 1<<(k*4+y);
35     return temp^state;
36 }
37 void bfs(){
38     while(rear>top){
39             int state = qState[top++];
40         for(int i=0;i<16;i++){
41             int temp = mve(state,i);
42 
43             if(state==65535){
44                 cout<<step[state]<<endl;
45                 int tt = top-1;
46                 while(f[tt].from!=-1){//输出位置。。
47                     cout<<f[tt].index/4+1<<" "<<f[tt].index%4+1<<endl;
48                     tt = f[tt].from;
49                 }
50                 return ;
51             }
52             else if(!flag[temp]){
53                 f[rear].from = top-1;//存其生成节点的信息。。
54                 f[rear].index = i;
55                 qState[rear++] = temp;
56                 flag[temp] = true;
57                 step[temp] = step[state]+1;
58             }
59         }
60     }
61 
62 }
63 
64 int main()
65 {
66     init();
67     bfs();
68 
69     return 0;
70 }