HDOJ 1043 eight

实际上和POJ 1077一样，但是这里有多组输入，并且有一组输入为12345678x（也就是不需要移动就达到了目标状态），这时还要输出一个空行。
  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     memset(Q, 0, sizeof(Q));
 68     memset(p, 0, sizeof(p));
 69     memset(vis, 0, sizeof(vis));
 70 
 71     Q[front = 1] = start;
 72     Q[rear = 2] = goal;
 73     vis[cantor(start)] = 1;
 74     vis[cantor(goal)] = 2;
 75 
 76     while (front <= rear)
 77     {
 78         cur = Q[front++];
 79         ct = cantor(cur);
 80         for (i = 0; cur.a[i] && i < N; ++i) ;
 81         x = i / 3;
 82         y = i % 3;
 83         for (i = 0; i < 4; ++i)
 84         {
 85             nx = x + d[i][0];
 86             ny = y + d[i][1];
 87             if (nx>=0 && nx<3 && ny>=0 && ny<3)
 88             {
 89                 nst = cur;
 90                 nst.a[x*3+y] = cur.a[nx*3+ny];
 91                 nst.a[nx*3+ny] = 0;
 92                 nt = cantor(nst);
 93                 if (!vis[nt])
 94                 {
 95                     Q[++rear] = nst;
 96                     p[nt].k = ct;
 97                     p[nt].d = i;
 98                     vis[nt] = vis[ct];
 99                 }
100                 else if (vis[ct] != vis[nt])
101                 {
102                     t = (vis[ct]==1 ? 1:0);
103                     print_path(t ? ct:nt, 0);
104                     putchar(md[t ? i:3-i]);
105                     print_path(t ? nt:ct, 1);
106                     putchar('\n');
107                     return ;
108                 }
109             }
110         }
111     }
112 }
113 
114 int main()
115 {
116     char i, c[5];
117     state start, goal;
118 
119     while(~scanf("%s", c))
120     {
121         start.a[0] = (c[0]=='x' ? 0:c[0]-'0');
122         for (i = 1; i < N; ++i)
123         {
124             scanf("%s", c);
125             start.a[i] = (c[0]=='x' ? 0:c[0]-'0');
126         }
127         goal.a[8] = 0;
128         for (i = 0; i < N-1; ++i)
129             goal.a[i] = i + 1;
130 
131         for (i = 0; start.a[i] == goal.a[i] && i < N; ++i) ;
132         if (i == N) puts("");
133         else if (bool_inv(start) != bool_inv(goal)) puts("unsolvable");
134         else bfs(start, goal);
135     }
136 
137     return 0;
138 }