经过去除 code 变量加上手写队列，把代码的时间优化了不少，但是看了一下 status，感觉压力很大，一帮的 0ms。。。。
code 是没用的记录，可以删除，成型代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int MAX = 500000;
struct Node {
int table;
int depth;
int last;
} start, queue[MAX];
int hash(int table, int op) {
int st;
st = (1 << op);
if (op % 4 > 0) st |= (1 << (op - 1));
if (op % 4 < 3) st |= (1 << (op + 1));
if (op / 4 > 0) st |= (1 << (op - 4));
if (op / 4 < 3) st |= (1 << (op + 4));
return (table ^ st);
}
int bfs() {
Node node, next;
int tail = 0, head = 0;
node.table = start.table;
node.depth = 0;
node.last = -1;
if (node.table == 0 || node.table == ((1 << 16) - 1)) return 0;
queue[head++] = node;
while (head != tail) {
node = queue[tail];
tail = (tail + 1) % MAX;
for (int i = node.last + 1; i < 16; i++) {
next.table = hash(node.table, i);
next.depth = node.depth + 1;
next.last = i;
if (next.table == 0 || next.table == ((1 << 16) - 1)) return next.depth;
queue[head] = next;
head = (head + 1) % MAX;
}
}
return -1;
}
int main() {
char str[10];
start.table = 0;
for (int i = 0; i < 4; i++) {
gets(str);
for (int j = 0; j < 4; j++) {
if (str[j] == 'b') {
start.table |= (1 << (i * 4 + j));
}
}
}
int ret = bfs();
if (ret == -1)
printf("Impossible\n");
else
printf("%d\n", ret);
return 0;
}
|