問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1198思路:
寬度優先搜索
tips:
1. 如何表示整個chessboard？
最簡單的方法是用二維數組，不過如果發現該chessboard是8X8的話，很自然地會想到是否可以用一個整數來表示
答案是肯定的，long long類型，不過可能unsigned long long會更合適，避免負數產生的影響呵呵
2. 如何判斷一個狀態是否被訪問過？
根據tips 1，我們使用一個unsigned long long來表示狀態，而如果用一個一維數組來表示其整個范圍顯然是不合適的
答案是利用HASH表，額...不是我自己想的，不過這個想法我是應該想到的，艾...繼續加油
HASH， 相當強大而簡單的方案 這里我是使用鏈接法來解決HASH沖突的
單向寬度優先搜索
剛提交的時候一直TLE， 結果我將HASH_MAX設置地更大之后，勉勉強強地通過了，汗...
1 #define BOARD 8
2 #define MOVE_MAX 8
3 #define PRIME 100007
4 #define HASH_MAX PRIME
5 #define is_set(i, j, state) (state & (((unsigned long long)1)<<((i)*BOARD+(j))))
6 #define set_bit(i, j, state) (state |= (((unsigned long long)1)<<((i)*BOARD+(j))))
7 #define clear_bit(i, j, state) (state &= (~(((unsigned long long)1)<<((i)*BOARD+(j)))))
8 #define is_valid(i, j) (i>=0 && i<BOARD && j>=0 && j<BOARD)
9 struct Node {
10 /* 8x8 chessboard can be represented by 64 bits */
11 unsigned long long state;
12 short move;
13 }queue[635376];
14 unsigned long long begin, end;
15 const int dx[] = {0, 0, -1, 1};
16 const int dy[] = {-1, 1, 0, 0};
17 int head, tail;
18 struct Hash {
19 unsigned long long *pstate;
20 struct Hash *next;
21 }hash_table[HASH_MAX];
22
23 int
24 check_hash(unsigned long long value)
25 {
26 int index = value % PRIME;
27 struct Hash *p = hash_table[index].next;
28 while(p != NULL) {
29 if(*(p->pstate) == value)
30 return 1;
31 p = p->next;
32 }
33 return 0;
34 }
35
36 void
37 insert_hash(unsigned long long *pstate, int index)
38 {
39 struct Hash *node = malloc(sizeof(struct Hash));
40 node->pstate = pstate;
41 node->next = hash_table[index].next;
42 hash_table[index].next = node;
43 }
44
45 int
46 bfs()
47 {
48 int i, j, x, y, next_x, next_y, cnt, cur_move=0;
49 unsigned long long cur_state, next_state;
50 queue[tail].state = begin;
51 queue[tail].move = 0;
52 insert_hash(&(queue[tail].state), (queue[tail].state)%PRIME);
53 while(head<tail && cur_move<=MOVE_MAX) {
54 ++head;
55 cnt = 0;
56 cur_state = queue[head].state;
57 cur_move = queue[head].move;
58 if(cur_state == end)
59 return 1;
60 for(i=0; i<64 && cnt<4; i++) {
61 if(cur_state & (((unsigned long long)1)<<i)) {
62 ++cnt;
63 x = i/BOARD;
64 y = i%BOARD;
65 for(j=0; j<4; j++) { /* left, right, up, down */
66 next_x = x + dx[j];
67 next_y = y + dy[j];
68 if(!is_valid(next_x, next_y))
69 continue;
70 if(is_set(next_x, next_y, cur_state)) {
71 next_x += dx[j];
72 next_y += dy[j];
73 if(!is_valid(next_x, next_y))
74 continue;
75 }
76 /* make sure the next state never showed before */
77 /* hash: one of the most powerful tools */
78 next_state = cur_state;
79 clear_bit(x, y, next_state);
80 set_bit(next_x, next_y, next_state);
81 if(!check_hash(next_state)) {
82 ++tail;
83 queue[tail].move = cur_move + 1;
84 queue[tail].state = next_state;
85 insert_hash(&(queue[tail].state), (queue[tail].state)%PRIME);
86 }
87 }
88 }
89 }
90 }
91 return 0;
92 }
雙向寬度優先搜索
當我們知道開始和結束狀態的條件下，可以采用雙向寬度優先搜索
而且可以大大減小需要搜索的狀態數目，因為需要搜索的層數減少一半
1 /* bidirectional BFS */
2 /* Memory: 2704K Time: 47MS */
3 #include<stdio.h>
4 #include<stdlib.h>
5 #include<string.h>
6
7 #define BOARD 8
8 #define MOVE_MAX 8
9 #define PRIME 10007
10 #define HASH_MAX PRIME
11 #define is_set(i, j, state) (state & (((unsigned long long)1)<<((i)*BOARD+(j))))
12 #define set_bit(i, j, state) (state |= (((unsigned long long)1)<<((i)*BOARD+(j))))
13 #define clear_bit(i, j, state) (state &= (~(((unsigned long long)1)<<((i)*BOARD+(j)))))
14 #define is_valid(i, j) (i>=0 && i<BOARD && j>=0 && j<BOARD)
15 struct Node {
16 /* 8x8 chessboard can be represented by 64 bits */
17 unsigned long long state;
18 short move;
19 }queue[63537], second_queue[63537];
20 unsigned long long begin, end;
21 const int dx[] = {0, 0, -1, 1};
22 const int dy[] = {-1, 1, 0, 0};
23 int head, tail, second_head, second_tail;
24 struct Hash {
25 unsigned long long *pstate;
26 struct Hash *next;
27 }hash_table[HASH_MAX], second_hash_table[HASH_MAX];
28
29 int
30 check_hash(struct Hash *hash, unsigned long long value)
31 {
32 int index = value % PRIME;
33 struct Hash *p = hash[index].next;
34 while(p != NULL) {
35 if(*(p->pstate) == value)
36 return 1;
37 p = p->next;
38 }
39 return 0;
40 }
41
42 void
43 insert_hash(struct Hash *hash, unsigned long long *pstate, int index)
44 {
45 struct Hash *node = malloc(sizeof(struct Hash));
46 node->pstate = pstate;
47 node->next = hash[index].next;
48 hash[index].next = node;
49 }
50
51 int
52 bfs()
53 {
54 int i, j, x, y, next_x, next_y, cnt, cur_move, second_cur_move;
55 cur_move = second_cur_move = 0;
56 unsigned long long cur_state, next_state;
57 queue[tail].state = begin;
58 queue[tail].move = 0;
59 insert_hash(hash_table, &(queue[tail].state), (queue[tail].state)%PRIME);
60 second_queue[second_tail].state = end;
61 second_queue[second_tail].move = 0;
62 insert_hash(second_hash_table, &(second_queue[second_tail].state), (second_queue[second_tail].state)%PRIME);
63 while(head<tail && second_head<second_tail) {
64 ++head;
65 cnt = 0;
66 cur_state = queue[head].state;
67 cur_move = queue[head].move;
68 for(i=0; i<64 && cnt<4; i++) {
69 if(cur_state & (((unsigned long long)1)<<i)) {
70 ++cnt;
71 x = i/BOARD;
72 y = i%BOARD;
73 for(j=0; j<4; j++) { /* left, right, up, down */
74 next_x = x + dx[j];
75 next_y = y + dy[j];
76 if(!is_valid(next_x, next_y))
77 continue;
78 if(is_set(next_x, next_y, cur_state)) {
79 next_x += dx[j];
80 next_y += dy[j];
81 if(!is_valid(next_x, next_y))
82 continue;
83 }
84 /* make sure the next state never showed before */
85 /* hash: one of the most powerful tools */
86 next_state = cur_state;
87 clear_bit(x, y, next_state);
88 set_bit(next_x, next_y, next_state);
89 if(!check_hash(hash_table, next_state) && cur_move<MOVE_MAX/2) {
90 if(check_hash(second_hash_table, next_state))
91 return 1;
92 ++tail;
93 queue[tail].move = cur_move + 1;
94 queue[tail].state = next_state;
95 insert_hash(hash_table, &(queue[tail].state), (queue[tail].state)%PRIME);
96 }
97 }
98 }
99 }
100 ++second_head;
101 cnt = 0;
102 cur_state = second_queue[second_head].state;
103 second_cur_move = second_queue[second_head].move;
104 for(i=0; i<64 && cnt<4; i++) {
105 if(cur_state & (((unsigned long long)1)<<i)) {
106 ++cnt;
107 x = i/BOARD;
108 y = i%BOARD;
109 for(j=0; j<4; j++) {
110 next_x = x + dx[j];
111 next_y = y + dy[j];
112 if(!is_valid(next_x, next_y))
113 continue;
114 if(is_set(next_x, next_y, cur_state)) {
115 next_x += dx[j];
116 next_y += dy[j];
117 if(!is_valid(next_x, next_y))
118 continue;
119 }
120 next_state = cur_state;
121 clear_bit(x, y, next_state);
122 set_bit(next_x, next_y, next_state);
123 if(!check_hash(second_hash_table, next_state) && second_cur_move<MOVE_MAX/2) {
124 if(check_hash(hash_table, next_state))
125 return 1;
126 ++second_tail;
127 second_queue[second_tail].move = second_cur_move + 1;
128 second_queue[second_tail].state = next_state;
129 insert_hash(second_hash_table, &(second_queue[second_tail].state), (second_queue[second_tail].state)%PRIME);
130 }
131 }
132 }
133 }
134 }
135 return 0;
136 }
137
138 int
139 main(int argc, char **argv)
140 {
141 int i, j, k;
142 while(scanf("%d %d", &i, &j) != EOF) {
143 head = second_head = -1;
144 tail = second_tail = 0;
145 begin = end = 0;
146 set_bit(i-1, j-1, begin);
147 memset(hash_table, 0, sizeof(hash_table));
148 memset(second_hash_table, 0, sizeof(second_hash_table));
149 memset(queue, 0, sizeof(queue));
150 memset(second_queue, 0, sizeof(second_queue));
151 for(k=1; k<4; k++) {
152 scanf("%d %d", &i, &j);
153 set_bit(i-1, j-1, begin);
154 }
155 for(k=0; k<4; k++) {
156 scanf("%d %d", &i, &j);
157 set_bit(i-1, j-1, end);
158 }
159 printf("%s\n", bfs()==1 ? "YES" : "NO");
160 }
161 }