题解
二分答案+Dinic最大流
二分答案(mid)
把门拆成(mid)个时间点的门
相邻时间的门连一条(inf)的边
预处理出每个门到每个人的最短时间
为(dis[k][i][j]) 在((i,j))的人到第(k)个门最短时间
然后一个人连向每个第(dis[k][i][j])那个时刻的门，容量为(1)
然后,源点连向每个人一条容量为(1)的边
所有门都连向汇点一条容量为(1)的边（其实只要每个最后一个时刻的门连一条容量为(mid)的边即可）
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
template<class T> inline void read(T &x) {
x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
x = f ? -x : x;
return ;
}
template<class T> inline void write(T x) {
if (!x) {putchar(48);return ;}
if (x < 0) x = -x, putchar('-');
int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 40, inf = 1e9;
int n, m;
int fx[4] = {1, 0, -1, 0};
int fy[4] = {0, 1, 0, -1};
char ch[N][N];
int dis[N<<2][N][N], door, people;
struct BB {
int x, y;
};
queue<BB> Q;
void BFS(int k, int xx, int yy) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dis[k][i][j] = inf;
dis[k][xx][yy] = 0; Q.push((BB) {xx, yy});
while (!Q.empty()) {
int x = Q.front().x, y = Q.front().y; Q.pop();
for (int w = 0; w < 4; w++) {
int i = x + fx[w], j = y + fy[w];
if (i < 1 || i > n || j < 1 || j > m || ch[i][j] != '.') continue;
if (dis[k][i][j] > dis[k][x][y]+1)
dis[k][i][j] = dis[k][x][y]+1, Q.push((BB) {i, j});
}
}
}
struct node {
int to, nxt, w;
}g[N*N*N*N];
int last[N*N*N], cur[N*N*N], dep[N*N*N], s, t, gl = 1, p[N][N];
inline void add(int a, int b, int c) {
g[++gl] = (node) {b, last[a], c};
last[a] = gl;
g[++gl] = (node) {a, last[b], 0};
last[b] = gl;
}
queue<int> q;
bool bfs() {
memset(dep, 0, sizeof(dep));
q.push(s); dep[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = last[u]; i; i = g[i].nxt) {
int v = g[i].to;
if (!dep[v] && g[i].w) {
dep[v] = dep[u]+1;
q.push(v);
}
}
}
return dep[t] == 0 ? 0 : 1;
}
int dfs(int u, int d) {
if (u == t) return d;
for (int &i = cur[u]; i; i = g[i].nxt) {
int v = g[i].to;
if (g[i].w && dep[v] == dep[u]+1) {
int di = dfs(v, min(d, g[i].w));
if (di) {
g[i].w -= di;
g[i^1].w += di;
return di;
}
}
}
return 0;
}
int Dinic() {
int ans = 0;
while (bfs()) {
for (int i = 1; i <= t; i++)
cur[i] = last[i];
while (int d = dfs(s, inf)) ans += d;
}
return ans;
}
int check(int mid) {
s = door*mid+people+1, t = s+1;
memset(last, 0, sizeof(last)); gl = 1;
for (int k = 1; k <= door; k++)
for (int z = 1; z <= mid; z++) {
if (z < mid)
add((k-1)*mid+z, (k-1)*mid+z+1, inf);
else add(k*mid, t, mid);
}
for (int i = 1; i <= people; i++)
add(s, door*mid+i, 1);
for (int k = 1; k <= door; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (ch[i][j] == '.' && dis[k][i][j] <= mid)
add(door*mid+p[i][j], (k-1)*mid+dis[k][i][j], 1);
return Dinic();
}
int main() {
read(n), read(m);
for (int i = 1; i <= n; i++)
scanf("%s", ch[i]+1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (ch[i][j] == 'D')
BFS(++door, i, j);
else if (ch[i][j] == '.') p[i][j] = ++people;
int l = 0, r = people, ans = 666666;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid) == people) r = mid-1, ans = mid;
else l = mid+1;
}
if (ans == 666666) puts("impossible");
else printf("%d
", ans);
return 0;
}