Bzoj 1054(BFS+状压判重)

Bzoj 1054
每个状态当做一个点,然后BFS
每次BFS在状态里找1然后遍历即可,判重就存一个16位的二进制就行了,而不需要哈希
二维数组转16位的二进制,16位的二进制转二维数组的方法具体实现看代码。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct data {int st, d;};
int gl[5][5];
int a[5][5];
char s[5];
bool vis[1 << 17];
int cura[5][5];
int getIntByArray() {
int st = 0, ret = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) ret += cura[i][j] * (1 << st), st++;
return ret;
}
void getArrayByInt(int a) {
int st = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) cura[i][j] = (a >> st) & 1, st++;
}
void clean() {
ms(vis, false);
}
void solve() {
clean();
for (int i = 1; i <= 4; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= 4; j++) {
cura[i][j] = a[i][j] = s[j] - '0';
}
}
for (int i = 1; i <= 4; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= 4; j++) {
gl[i][j] = s[j] - '0';
}
}
queue<data> q;
q.push((data){getIntByArray(), 0});
for (int x = 1; x <= 4; x++)
for (int y = 1; y <= 4; y++) cura[x][y] = gl[x][y];
int gl_ = getIntByArray();
while (!q.empty()) {
data p = q.front(); q.pop();
if (p.st == gl_) {
printf("%d\n", p.d);
return ;
}
getArrayByInt(p.st);
int nowa[5][5];
for (int x = 1; x <= 4; x++)
for (int y = 1; y <= 4; y++) nowa[x][y] = cura[x][y];
for (int x = 1; x <= 4; x++)
for (int y = 1; y <= 4; y++)
if (nowa[x][y] == 1)
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (tx > 0 && ty > 0 && tx <= 4 && ty <= 4 && nowa[tx][ty] == 0) {
swap(cura[x][y], cura[tx][ty]);
int tt = getIntByArray();
if (!vis[tt]) {
q.push((data){tt, p.d + 1});
vis[tt] = true;
}
swap(cura[x][y], cura[tx][ty]);
}
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
solve();
return 0;
}

------ 本文结束 ------