「BZOJ1189」紧急疏散evacuate

Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N×MN\times M的矩形区域。每个格子如果是.,那么表示这是一块空地;如果是X,那么表示这是一面墙,如果是D,那么表示这是一扇门,人们可以从这儿撤出房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格,当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

Input

第一行是由空格隔开的一对正整数NNMM3N203\leq N \leq 203M203\leq M\leq 20
以下NNMM列描述一个N×MN\times M的矩阵。其中的元素可为字符.XD,且字符间无空格。

Output

只有一个整数KK,表示让所有人安全撤离的最短时间,
如果不可能撤离,那么输出impossible(不包括引号)。

Sample Input

1
2
3
4
5
6
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX

Sample Output

1
3

Solution

二分答案假设枚举时间为midmid,把所有门拆成midmid个点,第ii个点对应第ii个时刻。
从所有的.向所有的D连边,注意.D的最短距离要mid\leq mid且从距离对应的时刻连边,其次在预处理的时候如果走到一个门,就breakbreak,因为你直接被传送走了,不能再走了。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 30*30*30, M= 30*30*30*30*3;
struct Edge {
int u, v, nxt, f;
}e[M * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en ,e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}


int n, m;

char str[40][40];
int d[23][23][23][23];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void work(int x, int y) {
queue<pii>q;
q.push(mk(x, y));
memset(d[x][y],0x3f, sizeof d[x][y]);
d[x][y][x][y] = 0;
while(!q.empty()) {
pii now = q.front(); q.pop();
for(int i = 0; i < 4; ++i) {
int r = now.fi + dx[i];
int c = now.se + dy[i];
if(r < 1 || r > n || c < 1 || c > m || d[x][y][r][c] < 0x3f3f3f3f || str[r][c] == 'X') continue;
d[x][y][r][c] = d[x][y][now.fi][now.se] + 1;
if(str[r][c] == 'D') continue;
q.push(mk(r, c));
}
}
}
int id[23][23], cnt;
int s, t;
void init() {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(str[i][j] == '.')
work(i, j), id[i][j] = ++cnt;
s = ++cnt;
t = ++cnt;
}
int dis[N];
bool bfs() {
queue<int>q;
q.push(s);
memset(dis,0,sizeof dis);
dis[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && !dis[e[i].v]) {
dis[e[i].v] = dis[x] + 1;
if(e[i].v == t) return 1;
q.push(e[i].v);
}
}
return 0;
}
const int inf = 1e9;
int dinic(int x, int flow) {
if(x == t) return flow;
int rest = flow, k;
for(int i = head[x]; rest && i; i = e[i].nxt) if(e[i].f && dis[e[i].v] == dis[x] + 1) {
k = dinic(e[i].v, min(e[i].f, rest));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(flow == rest) dis[x] = 0;
return flow - rest;
}
bool check(int mid) {
int tmp = cnt;
en = 1;
memset(head,0,sizeof head);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) if(str[i][j] == 'D') {
if(mid == 0) continue;
int l = ++tmp;
tmp += mid - 1;
int r = tmp;
for(int x = 1; x <= n; ++x)
for(int y = 1; y <= m; ++y) if(str[x][y] == '.' && d[x][y][i][j] <= mid) {
for(int k = l + d[x][y][i][j] - 1; k <= r; ++k)
addedge(id[x][y], k, 1);
}
for(int k = l; k <= r; ++k)
addedge(k, t, 1);
} else if(str[i][j] == '.') addedge(s, id[i][j], 1);
int y, res = 0;
while(bfs()) while(y = dinic(s, inf)) res += y;
return res == cnt - 2;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; ++i)
scanf("%s", str[i] + 1);
init();
int l = -1, r = n * m + 1;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(r == n * m + 1) {
puts("impossible");
} else writeln(r);
return 0;
}