POJ 1077 eight

双广，16MS，相当快。

  1 # include <stdio.h>
  2 # include <string.h>
  3 
  4 # define MAXN (362880 + 5)
  5 
  6 typedef struct 
  7 {
  8     char a[9];
  9 }state;
 10 
 11 typedef struct
 12 {
 13     int k;
 14     char d;
 15 }path;
 16 
 17 path p[MAXN];
 18 const char md[4] = {'u','l','r','d'};
 19 const int dir[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
 20 int fact[9];
 21 
 22 int front, rear;
 23 state cur, nst;            /* new state */
 24 char vis[MAXN];
 25 char dist[MAXN];        /* 求的是最短距离( < 100)，可以用 char 类型 */
 26 state Q[MAXN/2];
 27 
 28 void print_path(int x, char f);
 29 char equal(state x, state y);
 30 void read(state *s);
 31 int inversions(state s);
 32 int cantor(state s);
 33 void init_fact(void);
 34 int bfs_d(state start, state goal);
 35 
 36 int main()
 37 {
 38     int i;
 39     state start, goal;
 40     
 41     init_fact();
 42 
 43     read(&start);
 44     goal.a[8] = 0;
 45     for (i = 0; i < 8; ++i)
 46         goal.a[i] = i + 1;
 47 
 48     if (inversions(start)%2 == inversions(goal)%2)
 49     {
 50         if (equal(start, goal)) putchar('\n');
 51         else bfs_d(start, goal);
 52     }
 53     else puts("unsolvable");
 54 
 55     return 0;
 56 }
 57 
 58 int bfs_d(state start, state goal)
 59 {
 60     int i, x, y, nx, ny, ct, nt;
 61 
 62     memset(vis, 0, sizeof(vis));
 63     memset(dist, 0, sizeof(dist));
 64 
 65     front = 1;
 66     Q[front] = start;
 67     rear = 2;
 68     Q[rear++] = goal;
 69     vis[cantor(start)] = 1;                /* 1 表示从起始节点扩展得到 */
 70     vis[cantor(goal)] = 2;                 /* 2 表示从目标节点扩展得到 */
 71 
 72     while (front < rear)
 73     {
 74         cur = Q[front++];
 75         ct = cantor(cur);
 76         for (i = 0; cur.a[i] && i < 9; ++i) ;
 77         x = i / 3;
 78         y = i % 3;
 79         for (i = 0; i < 4; ++i)
 80         {
 81             nx = x + dir[i][0];
 82             ny = y + dir[i][1];
 83             if (nx>=0 && nx<3 && ny>=0 && ny<3)
 84             {
 85                 nst = cur;
 86                 nst.a[x*3+y] = cur.a[nx*3+ny];
 87                 nst.a[nx*3+ny] = 0;
 88                 if (!vis[nt = cantor(nst)])
 89                 {
 90                     Q[rear++] = nst;
 91                     p[nt].k = ct;
 92                     p[nt].d = i;
 93                     dist[nt] = dist[ct] + 1;
 94                     vis[nt] = vis[ct];
 95                 }
 96                 else if (vis[ct] != vis[nt])
 97                 {
 98                     if (vis[ct] == 1)
 99                     {
100                         print_path(ct, 0);
101                         putchar(md[i]);
102                         print_path(nt, 1);
103                     }
104                     else
105                     {
106                         print_path(nt, 0);
107                         putchar(md[3-i]);
108                         print_path(ct, 1);
109                     }
110                     return 1 + dist[nt] + dist[ct];
111                 }
112             }
113         }
114     }
115 
116     return -1;
117 }
118 
119 void read(state *s)
120 {
121     int i;
122     char c[5];
123 
124     for (i = 0; i < 9; ++i)
125     {
126         scanf("%s", c);
127         if (c[0] == 'x') (*s).a[i] = 0;
128         else (*s).a[i] = c[0] - '0';
129     }
130 }
131 
132 int inversions(state s)
133 {
134     char ch;
135     int i, j, ret;
136 
137     ret = 0;
138     for (i = 0; i < 9; ++i)
139     {
140         if (s.a[i] == 0) continue;
141         ch = s.a[i];
142         for (j = i+1; j < 9; ++j)
143         {
144             if (s.a[j] < ch && s.a[j] != 0)
145                 ++ret;
146         }
147     }
148 
149     return ret;
150 }
151 
152 int cantor(state s)
153 {
154     char ch;
155     int i, j, ret, cnt;
156 
157     ret = 0;
158     for (i = 0; i < 9; ++i)
159     {
160         cnt = 0;
161         ch = s.a[i];
162         for (j = i+1; j < 9; ++j)
163         {
164             if (s.a[j] < ch)
165                 ++cnt;
166         }
167         ret += cnt*fact[8-i];
168     }
169 
170     return ret;
171 }
172 
173 void init_fact(void)
174 {
175     int i;
176 
177     fact[0] = 1;
178     for (i = 1; i < 9; ++i)
179     {
180         fact[i] = i * fact[i-1];
181     }
182 }
183 
184 void print_path(int x, char f)
185 {
186     if (p[x].k == 0) return;
187     if (!f)
188     {
189         print_path(p[x].k, f);
190         putchar(md[p[x].d]);
191     }
192     else
193     {
194         putchar(md[3-p[x].d]);
195         print_path(p[x].k, f);
196     }
197 }
198 
199 char equal(state x, state y)
200 {
201     int i;
202 
203     for (i = 0; i < 9; ++i)
204         if (x.a[i] != y.a[i]) return 0;
205 
206     return 1;
207 }

有点长。

*********************************************************

优化了一下：16MS（C）

  1 # include <stdio.h>
  2 # include <string.h>
  3 
  4 # define N 9    
  5 # define MAXN (362880 + 10)
  6 
  7 typedef struct{ int k; char d; }foot;
  8 typedef struct{    char a[N]; }state;
  9 
 10 const char md[4] = {'u', 'l', 'r', 'd'};
 11 const char d[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};                                                    
 12 const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 720*7, 720*56};
 13 
 14 state Q[MAXN/10];
 15 char vis[MAXN];
 16 foot p[MAXN];
 17 
 18 int cantor(state s)
 19 {
 20     char ch;
 21     int i, j, cnt, ret;
 22 
 23     ret = 0;
 24     for (i = 0; i < N-1; ++i)
 25     {
 26         cnt = 0;
 27         ch = s.a[i];
 28         for (j = i+1; j < N; ++j)
 29             if (s.a[j] < ch) ++cnt;
 30         ret += cnt*fact[8-i];
 31     }
 32 
 33     return ret;
 34 }
 35 
 36 char bool_inv(state s)
 37 {
 38     char ch, ret;
 39     int i, j;
 40     
 41     ret = 0;
 42     for (i = 0; i < N-1; ++i)
 43     {
 44         if ((ch = s.a[i]) == 0) continue;
 45         for (j = i+1; j < N; ++j)
 46             if (s.a[j] && s.a[j] < ch) ret = 1 - ret;
 47     }
 48     
 49     return ret;
 50 }
 51 
 52 void print_path(int x, char f)
 53 {
 54     if (p[x].k == 0) return ;
 55     if (f) putchar(md[3-p[x].d]);
 56     print_path(p[x].k, f);
 57     if (!f) putchar(md[p[x].d]);
 58 }
 59 
 60 void bfs(state start, state goal)
 61 {
 62     char t;
 63     state cur, nst;
 64     int front, rear, i;
 65     int x, y, nx, ny, ct, nt;
 66     
 67     Q[front = 1] = start;
 68     Q[rear = 2] = goal;
 69     vis[cantor(start)] = 1;
 70     vis[cantor(goal)] = 2;
 71     
 72     while (front <= rear)
 73     {
 74         cur = Q[front++];
 75         ct = cantor(cur);
 76         for (i = 0; cur.a[i] && i < N; ++i) ;
 77         x = i / 3;  y = i % 3;
 78         for (i = 0; i < 4; ++i)
 79         {
 80             nx = x + d[i][0];  ny = y + d[i][1];
 81             if (nx>=0 && nx<3 && ny>=0 && ny<3)
 82             {
 83                 nst = cur;
 84                 nst.a[x*3+y] = cur.a[nx*3+ny];
 85                 nst.a[nx*3+ny] = 0;
 86                 nt = cantor(nst);
 87                 if (!vis[nt])
 88                 {
 89                     Q[++rear] = nst;
 90                     p[nt].k = ct;
 91                     p[nt].d = i;
 92                     vis[nt] = vis[ct];
 93                 }
 94                 else if (vis[ct] != vis[nt])
 95                 {
 96                     t = (vis[ct]==1 ? 1:0);
 97                     print_path(t ? ct:nt, 0);
 98                     putchar(md[t ? i:3-i]);
 99                     print_path(t ? nt:ct, 1);
100                     putchar('\n');
101                     return ;
102                 }
103             }
104         }
105     }
106 }
107 
108 int main()
109 {
110     char i, c[5];
111     state start, goal;
112 
113     for (i = 0; i < N; ++i)
114     {
115         scanf("%s", c);
116         start.a[i] = (c[0]=='x' ? 0:c[0]-'0');
117     }
118     goal.a[8] = 0;
119     for (i = 0; i < N-1; ++i)
120         goal.a[i] = i + 1;
121         
122     for (i = 0; start.a[i] == goal.a[i] && i < N; ++i) ;
123     if (i == N) puts("");
124     else if (bool_inv(start) != bool_inv(goal)) puts("unsolvable");
125     else bfs(start, goal);
126 
127     return 0;
128 }