紫书—八数码问题（BFS）

 1 #include<cstdio>
 2 #include<set>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 typedef int State[9];
 7 const int maxstate = 1000000;
 8 State st[maxstate],goal;
 9 int dist[maxstate];
10 int fa[maxstate];
11 
12 const int dx[]={-1,1,0,0};
13 const int dy[]={0,0,-1,1};
14 //使用set STL
15 set<int> vis;
16 void init_lookup_table(){vis.clear();}
17 int try_to_insert(int s){
18     int v=0;
19     for(int i=0;i<9;i++) v=v*10+st[s][i];
20     if(vis.count(v)) return 0;
21     vis.insert(v);
22     return 1;
23 }
24 
25 //使用哈希
26 /*const int hashsize = 1000003;
27 int head[hashsize],Next[maxstate];
28 void init_lookup_table(){memset(head,0,sizeof(head));}
29 
30 int hash(State& s){
31     int v=0;
32     for(int i=0;i<9;i++) v=v*10+s[i];
33     return v % hashsize;
34 }
35 
36 int try_to_insert(int s){
37     int h = hash(st[s]);
38     int u = head[h];
39     while(u){
40         if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
41         u=Next[u];
42     }
43     Next[s]=head[h];
44     head[h]=s;
45     return 1;
46 }*/
47 
48 int bfs(){
49     init_lookup_table();
50     int front = 1,rear=2;
51     while(front<rear){
52         State &s=st[front];
53         if(memcmp(goal,s/*st[front]*/,sizeof(s))==0) return front;
54         int z;
55         for(z=0;z<9;z++) if(!s[z]) break;
56         int x=z/3,y=z%3;
57         for(int d=0;d<4;d++){
58             int newx=x+dx[d];
59             int newy=y+dy[d];
60             int newz=newx*3+newy;
61             if(newx>=0 && newx<3 && newy>=0 && newy<3){
62                 State& t=st[rear];
63                 memcpy(&t,&s,sizeof(s));
64                 //memcpy(st[rear],st[front],sizeof(st[front]));
65                 t[newz]=s[z];
66                 t[z]=s[newz];
67                 /*st[rear][newz]=st[front][z];
68                 st[rear][z]=st[front][newz];*/
69                 dist[rear] = dist[front]+1;
70                 if(try_to_insert(rear)) rear++;
71             }
72         }
73         front++;
74     }
75     return 0;
76 }
77 
78 int main(){
79     for(int i=0;i<9; i++) scanf("%d",&st[1][i]);
80     for(int i=0;i<9; i++) scanf("%d",&goal[i]);
81     int ans=bfs();
82     if(ans>0) printf("%d\n",dist[ans]); else printf("-1\n");
83     return 0;
84 }