$B-BFS$泛做

$B-BFS$其实就是Binary-system BFS的简写,或者更详细的说只是一种建图的方式。

Preface

就是瞎做题,最近在一股脑把做过的题都整理一遍……包括水题

A [HAOI2008]移动玩具

bzoj1054

据说做这种题会有什么很奇妙的做法,但我的做法就是给每个二进制状态标一个号,sb连边之后再去暴力BFS求最短路……反正就是一道SB题就对了。

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>

#define MAXN 20
#define rr register
#define zt (1 << 16)

using namespace std ;
struct Edge{
int to, next ;
}E[zt << 6] ; int head[zt << 1], ct ;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1} ;
int N, S, T_, A[MAXN][MAXN][MAXN], T[MAXN][MAXN], t[MAXN], dist[zt << 1] ;

inline void Add(int u, int v){
E[++ ct].to = v, E[ct].next = head[u], head[u] = ct ;
E[++ ct].to = u, E[ct].next = head[v], head[v] = ct ;
}
int que[zt << 5] ;
inline void BFS(){
#define to(k) E[k].to
register int he = 1, ta = 0 ;
dist[S] = 1, que[++ ta] = S;
while (he <= ta){
rr int now = que[he ++] ;
for (rr int k = head[now] ; k ; k = E[k].next)
if (!dist[to(k)]) dist[to(k)] = dist[now] + 1, que[++ ta] = to(k) ;
if (dist[T_]) return ;
}
}
int main(){
// freopen("1054.in", "r", stdin) ;
// freopen("1054.out", "w", stdout) ;
N = (1 << 16) - 1 ;
for (rr int i = 0 ; i <= N ; ++ i){
memset(t, 0, sizeof(t)) ;
register int kans = 0, tot = 0, cnt = 0 ;
for (rr int j = 1 ; j <= 4 ; ++ j)
for (rr int k = 1 ; k <= 4 ; ++ k)
T[j][k] = (1 << tot & i) ? 1 : 0, ++ tot ;/*, cout << T[j][k] << " " ;
cout << "==================================" << endl ; */
tot = 0 ;/*
for (k = 1 ; k <= 4 ; ++ k)
for (l = 1 ; l <= 4 ; ++ l)
kans |= ((1 & T[k][l]) << tot), ++ tot ;
cout << kans << endl ; */
for (rr int j = 1 ; j <= 4 ; ++ j)
for (rr int k = 1 ; k <= 4 ; ++ k)
if (T[j][k])
for (rr int l = 0 ; l < 4 ; ++ l){
register int kx = j + dx[l], ky = k + dy[l] ;
if (kx < 1 || ky < 1 || kx > 4 || ky > 4 || T[kx][ky]) continue ;
memcpy(A[++ cnt], T, sizeof(T)), A[cnt][kx][ky] = 1, A[cnt][j][k] = 0 ;
}
tot = 0 ;
for (rr int j = 1 ; j <= cnt ; ++ j, tot = 0){
for (rr int k = 1 ; k <= 4 ; ++ k)
for (rr int l = 1 ; l <= 4 ; ++ l)
t[j] |= (1 & A[j][k][l]) << tot, ++ tot ;
Add(i, t[j]) ;
}
}
register int tot = 0 ;
for (rr int i = 1 ; i <= 4 ; ++ i)
for (rr int j = 1 ; j <= 4 ; ++ j)
scanf("%1d", &T[i][j]), S = S | ((1 & T[i][j]) << tot), ++ tot ;
tot = 0 ;
for (rr int i = 1 ; i <= 4 ; ++ i)
for (rr int j = 1 ; j <= 4 ; ++ j)
scanf("%1d", &T[i][j]), T_ = T_ | ((1 & T[i][j]) << tot) , ++ tot ;
BFS() ; cout << dist[T_] - 1 << endl ;
}

B 黑白棋游戏

Luogu1225

其实还是上面个sb题,但是我们要输出方案,于是我们就可以套个struct+stack输出方案:

哦,对了,Pre可以在BFS里面处理出来。

1
2
3
4
5
6
7
BFS() ; cout << dist[T_] - 1 << endl ; 
while (Pre[T_]){
int P[4], num = 0 , kans = T_ ^ Pre[T_] ;
for (rr int i = 0 ; i < 16 ; ++ i) if (kans & (1 << i)) P[++ num] = i + 1 ;
ans.push( (Ans){P[1] / 4 + (bool)(P[1] % 4), ((P[1] % 4) ? P[1] % 4 : 4), P[2] / 4 + (bool)(P[2] % 4), ((P[2] % 4) ? P[2] % 4 : 4)}), T_ = Pre[T_] ;
}
while (!ans.empty()) cout << ans.top().a << ans.top().b << ans.top().c << ans.top().d << endl, ans.pop() ;