ZOJ 1217 eight

八数码，双广、A*都超时了（可能是写得不好），IDA*通过了；
在POJ上是16MS（和双广一样，A* 60MS左右），HDOJ上是800MS左右（双广是500MS），ZOJ上只有IDA*没超时（2480MS）。
  1 # include <stdio.h>
  2 # include <math.h>
  3 # include <string.h>
  4 
  5 # define MIN(x, y) ((x)<(y) ? (x):(y))
  6 
  7 # define N 9
  8 # define DIR_N 4
  9 # define INF 0x7fffffff
 10 # define MAX_DEPTH 1000
 11 # define SIZE 3
 12 
 13 char solved;
 14 char start[N], goal[N];
 15 char cur[N];
 16 
 17 int bound;
 18 const char md[] = {'u', 'l', 'r', 'd'};
 19 const short int dir[][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
 20 char path[MAX_DEPTH];
 21 
 22 void solve(void);
 23 char read(char *s);
 24 int IDAstar(void);
 25 char bool_inv(char *s);
 26 int heu(void);
 27 int dfs(int zero_pos, int depth, char direction);
 28 
 29 int main()
 30 {
 31     int i;
 32     
 33     for (i = 0; i < N-1; ++i)
 34         goal[i] = i + 1;
 35     goal[N-1] = 0;
 36     while (read(start))
 37     {
 38         memcpy(cur, start, N);
 39         solve();
 40     }
 41     
 42     return 0;
 43 }
 44 
 45 void solve()
 46 {
 47     int i, depth;
 48 
 49     if (bool_inv(start) != bool_inv(goal)) puts("unsolvable");
 50     else
 51     {
 52         memset(path, -1, sizeof(path));
 53         depth = IDAstar();
 54         for (i = 0; path[i]!=-1; ++i)
 55         {
 56             putchar(md[path[i]]);
 57         }
 58         putchar('\n');
 59     }
 60 }
 61 
 62 char read(char *s)
 63 {
 64     char c[5];
 65     int i;
 66 
 67     if (EOF == scanf("%s", c)) return 0;
 68     else s[0] = (c[0]=='x' ? 0:c[0]-'0');
 69     for (i = 1; i < N; ++i)
 70     {
 71         scanf("%s", c);
 72         s[i] = (c[0]=='x' ? 0:c[0]-'0');
 73     }
 74     
 75     return 1;
 76 }
 77 
 78 int IDAstar(void)
 79 {
 80     int i;
 81 
 82     solved = 0;
 83     bound = heu();
 84 
 85     for (i = 0; start[i] && i < N; ++i) ;
 86 
 87     while (!solved && bound<100)
 88     {
 89         bound = dfs(i, 0, -10);
 90     }
 91 
 92     return bound;
 93 }
 94 
 95 int dfs(int pos, int depth, char d)
 96 {
 97     int h, i, nx, ny, npos, nbound, t;
 98 
 99     h = heu();
100 
101     if (depth+h > bound) return depth+h;
102     if (h == 0)
103     {
104        /* printf("depth = %d.\n", depth); */
105         solved = 1;
106         return depth;
107     }
108 
109     nbound = INF;
110     for (i = 0; i < DIR_N; ++i)
111     {
112         if (i+d == DIR_N-1) continue;
113         nx = pos/SIZE + dir[i][0];
114         ny = pos%SIZE + dir[i][1];
115         if (0<=nx && nx<SIZE && 0<=ny && ny<SIZE)
116         {
117             path[depth] = i;
118             npos = nx*SIZE + ny;
119             cur[pos] = cur[npos]; cur[npos] = 0;     /* pos -> npos */
120             t = dfs(npos, depth+1, i);
121             if (solved) return t;
122             nbound = MIN(nbound, t);
123             cur[npos] = cur[pos]; cur[pos] = 0;
124         }
125     }
126     return nbound;
127 }
128 
129 int heu(void)            /* return heu(cur_state) */
130 {
131     char ch;
132     int i, j, ret;
133 
134     ret = 0;
135     for (i = 0; i < N; ++i)
136     {
137         ch = goal[i];
138         if (ch == 0) continue;
139         for (j = 0; j < N; ++j)
140         {
141             if (ch == cur[j])
142             {
143                 ret = ret + abs(i/SIZE-j/SIZE) + abs(i%SIZE-j%SIZE);
144             }
145         }
146     }
147 
148     return ret;
149 }
150 
151 char bool_inv(char *s)
152 {
153     char ch, ret;
154     int i, j;
155 
156     ret = 0;
157     for (i = 0; i < N-1; ++i)
158     {
159         if ((ch = s[i]) == 0) continue;
160         for (j = i+1; j < N; ++j)
161         {
162             if (s[j] && s[j]<ch) ret = 1 - ret;
163         }
164     }
165 
166     return ret;
167 }