1 #include<cstdio>
 2 #include<iostream>
 3 #include<map>
 4 #include<queue> 
 5 
 6 using namespace std;
 7 
 8 int a[3][3],n;
 9 int ans = 123804765; 
10 const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
11 map<int,int> m;
12 
13 inline void bfs() {
14     queue<long long> q;
15     q.push(n);
16     m[n] = 0;
17     while(!q.empty()) {
18         int u = q.front();
19         q.pop();
20         int x = 0,y= 0,n = u;
21         if(u == ans) break;
22         for(int i = 2;i >= 0; i--)
23             for(int j = 2;j >= 0; j--) {
24                 a[i][j] = n % 10;
25                 n /= 10;
26                 if(!a[i][j]) x = i,y = j;
27             }
28         for(int i = 0;i < 4; i++) {
29             int nx = x + dx[i],ny = y + dy[i],ns = 0;
30             if(nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;
31             swap(a[nx][ny],a[x][y]);
32             for(int i = 0;i <= 2; i++)
33                 for(int j = 0;j <= 2; j++)
34                     ns = ns * 10 + a[i][j];
35             if(!m.count(ns)) {
36                 m[ns] = m[u] + 1;
37                 q.push(ns);
38             }
39             swap(a[nx][ny],a[x][y]);
40         }
41     }
42 }
43 
44 int main()
45 {
46     scanf("%d",&n);
47     bfs();
48     printf("%d",m[123804765]);
49     return 0;
50 }

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<map>
 5 
 6 using namespace std;
 7 
 8 int a[4][4],n,n1 = 123804765; 
 9 int x,y;
10 int wayx[4] = {1,-1,0,0},wayy[4] = {0,0,1,-1};
11 map<int,int> p,sum;
12 
13 inline void juzhen(int o) {
14     for(int i = 3;i >= 1; i--)
15         for(int j = 3;j >= 1; j--) {
16             a[i][j] = o % 10;
17             o /= 10;
18             if(a[i][j] == 0) x = i,y = j;
19         } 
20 }
21 
22 inline void double_bfs() {
23     if(n1 == 0) return ;
24     queue<int> step[2];
25     step[0].push(n);
26     step[1].push(n1);
27     sum[n] = 0;
28     sum[n1] = 0;
29     p[n] = 0;p[n1] = 1;
30     int deep = 0,s;
31     while(!step[0].empty() || !step[1].empty()) {
32         int i = 0;
33         while(i < 2) {
34             if(sum[step[i].front()] != deep) {
35                 i++;
36                 continue;
37             }
38             s = step[i].front();
39             step[i].pop();
40             juzhen(s);
41             for(int w = 0;w < 4; w++) {
42                 int xx = x + wayx[w];
43                 int yy = y + wayy[w];
44                 if(xx < 1 || xx > 3 || yy < 1 || yy > 3) continue;
45                 swap(a[x][y],a[xx][yy]);
46                 int pp = 0;
47                 for(int j = 1;j <= 3; j++)
48                     for(int u = 1;u <= 3; u++) 
49                         pp = pp * 10 + a[j][u];
50                 if(p.count(pp)) {
51                     if(p[pp] == 1 - i) {
52                         if(p[pp] == 0)
53                             printf("%d",(deep + 1) * 2);
54                         else 
55                             printf("%d",deep * 2 + 1);
56                         return ;
57                     }
58                 }
59                 else {
60                     step[i].push(pp);
61                     sum[pp] = sum[s] + 1;
62                     p[pp] = i;
63                 }
64                 swap(a[x][y],a[xx][yy]);
65             }
66         }
67         deep++;
68     }
69 }
70 
71 inline void tepan() {
72     if(n == n1) printf("0");
73     if(n == n1) n = n1 = 0;
74 }
75 
76 int main()
77 {
78     scanf("%d",&n);
79     tepan();
80     double_bfs();
81     return 0;
82 }