問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077思路:
傳說中經典的經典
解法有: 單向BFS，雙向BFS，還有A*等啟發式搜索算法
今天先寫了前兩種方法的代碼，至于啟發式算法待續
判重: 全排列的哈希，詳見:
http://www.shnenglu.com/Joe/archive/2010/08/06/122410.html代碼(單向BFS，110MS):
1 #define RC 3
2 #define STR_LEN 9
3 #define HASH_LEN 362880 /* 9! */
4 const int facs[] = {1, 2, 6, 24, 120, 720, 5040, 40320};
5 const char letters[] = "udlr";
6 const int dx[] = {-1, 1, 0, 0};
7 const int dy[] = {0, 0, -1, 1};
8 char success[] = "123456780";
9 char begin[STR_LEN+1];
10 int success_hash, begin_position;
11 int hash[HASH_LEN];
12 struct EACH {
13 char str[STR_LEN+1];
14 int position;
15 int pre;
16 int dir;
17 } queue[HASH_LEN];
18
19 /* permutation -> number */
20 int
21 hash_func(char *str)
22 {
23 int i, j, cnt, result = 0;
24 for(i=1; i<STR_LEN; i++) {
25 cnt = 0;
26 for(j=0; j<i; j++)
27 if(str[j] > str[i])
28 ++cnt;
29 result += (cnt*facs[i-1]);
30 }
31 return result;
32 }
33
34 void
35 init()
36 {
37 int i;
38 char input[2];
39 memset(hash, 0, sizeof(hash));
40 for(i=0; i<STR_LEN; i++) {
41 scanf("%s", input);
42 begin[i] = input[0];
43 if(begin[i] == 'x') {
44 begin[i] = '0';
45 begin_position = i;
46 }
47 }
48 begin[STR_LEN] = '\0';
49 success_hash = hash_func(success);
50 }
51
52 void
53 output(int index)
54 {
55 if(queue[index].pre == -1)
56 return;
57 output(queue[index].pre);
58 printf("%c", letters[queue[index].dir]);
59 }
60
61 #define ADD(tail, s, pos, p, d) strcpy(queue[tail].str, s); \
62 queue[tail].position = pos; \
63 queue[tail].pre = p; \
64 queue[tail].dir = d;
65
66 #define CHECK(h) if(h == success_hash) { \
67 output(tail); \
68 printf("\n"); \
69 return; \
70 }
71
72 void
73 bfs()
74 {
75 int i, h, head, tail;
76 char nxt[STR_LEN+1];
77 int curx, cury, nxtx, nxty;
78 head = -1;
79 tail = 0;
80 ADD(tail, begin, begin_position, -1, -1);
81 h = hash_func(begin);
82 hash[h] = 1;
83 CHECK(h);
84 while(head < tail) {
85 ++head;
86 curx = queue[head].position/RC;
87 cury = queue[head].position%RC;
88 for(i=0; i<4; i++) {
89 nxtx = curx + dx[i];
90 nxty = cury + dy[i];
91 if(nxtx>=0 && nxtx<RC && nxty>=0 && nxty<RC) {
92 strcpy(nxt, queue[head].str);
93 nxt[queue[head].position] = nxt[nxtx*RC+nxty];
94 nxt[nxtx*RC+nxty] = '0';
95 h = hash_func(nxt);
96 if(!hash[h]) {
97 ++tail;
98 ADD(tail, nxt, nxtx*RC+nxty, head, i);
99 hash[h] = 1;
100 CHECK(h);
101 }
102 }
103 }
104 }
105 printf("unsolvable\n");
106 }
代碼(雙向BFS，16MS):
1 #define RC 3
2 #define STR_LEN 9
3 #define HASH_LEN 362880 /* 9! */
4 const int facs[] = {1, 2, 6, 24, 120, 720, 5040, 40320};
5 const char letters[] = "udlr";
6 const int pos[] = {-3, 3, -1, 1}; /* up, down, left, right */
7 const int movable[][4] = {0,1,0,1, 0,1,1,1, 0,1,1,0, 1,1,0,1, 1,1,1,1, 1,1,1,0, 1,0,0,1, 1,0,1,1, 1,0,1,0};
8 int hash[2][HASH_LEN];
9 struct EACH {
10 char str[STR_LEN+1];
11 int position, pre, dir, hval;
12 } queue[2][HASH_LEN];
13
14 /* permutation -> number */
15 int
16 hash_func(char *str)
17 {
18 int i, j, cnt, result = 0;
19 for(i=1; i<STR_LEN; i++) {
20 cnt = 0;
21 for(j=0; j<i; j++)
22 if(str[j] > str[i])
23 ++cnt;
24 result += (cnt*facs[i-1]);
25 }
26 return result;
27 }
28
29 void
30 output(int hash_value)
31 {
32 int i, j;
33 char tmp[250];
34 for(i=0; i<HASH_LEN; i++)
35 if(queue[0][i].hval == hash_value)
36 break;
37 j = 0;
38 while(queue[0][i].pre != -1) {
39 tmp[j++] = letters[queue[0][i].dir];
40 i = queue[0][i].pre;
41 }
42 for(i=j-1; i>=0; i--)
43 printf("%c", tmp[i]);
44
45 for(i=0; i<HASH_LEN; i++)
46 if(queue[1][i].hval == hash_value)
47 break;
48 while(queue[1][i].pre != -1) {
49 printf("%c", queue[1][i].dir%2==0 ? letters[queue[1][i].dir+1] : letters[queue[1][i].dir-1]);
50 i = queue[1][i].pre;
51 }
52 }
53
54 #define ADD(index, tail, s, pos, p, d, h) strcpy(queue[index][tail].str, s); \
55 queue[index][tail].position = pos; \
56 queue[index][tail].pre = p; \
57 queue[index][tail].dir = d; \
58 queue[index][tail].hval = h;
59
60 int
61 bfs(char *start_str, int start_pos)
62 {
63 int i, index, h, curp, nxtp, head[2], tail[2];
64 char suc[] = "123456780";
65 char nxt[STR_LEN+1];
66 head[0] = head[1] = -1;
67 tail[0] = tail[1] = 0;
68 h = hash_func(start_str);
69 hash[0][h] = 1;
70 ADD(0, tail[0], start_str, start_pos, -1, -1, h);
71 h = hash_func(suc);
72 hash[1][h] = 1;
73 ADD(1, tail[1], suc, 8, -1, -1, h);
74 while(head[0]<tail[0] && head[1]<tail[1]) {
75 for(index=0; index<2; index++) {
76 ++head[index];
77 curp = queue[index][head[index]].position;
78 for(i=0; i<4; i++) {
79 if(movable[curp][i]) {
80 nxtp = curp + pos[i];
81 strcpy(nxt, queue[index][head[index]].str);
82 nxt[curp] = nxt[nxtp];
83 nxt[nxtp] = '0';
84 h = hash_func(nxt);
85 if(!hash[index][h]) {
86 ++tail[index];
87 ADD(index, tail[index], nxt, nxtp, head[index], i, h);
88 hash[index][h] = 1;
89 }
90 if(hash[1-index][h])
91 return h;
92 }
93 }
94 }
95 }
96 return -1;
97 }
98
99 int
100 main(int argc, char **argv)
101 {
102 int i, sp, h;
103 char input[2], num[STR_LEN+1];
104 for(i=0; i<STR_LEN; i++) {
105 scanf("%s", input);
106 num[i] = input[0];
107 if(num[i]=='x') {
108 num[i] = '0';
109 sp = i;
110 }
111 }
112 num[STR_LEN] = '\0';
113 h = bfs(num, sp);
114 if(h==-1)
115 printf("unsolvable\n");
116 else {
117 output(h);
118 printf("\n");
119 }
120 return 0;
121 }