题目链接：紧急疏散
这薄脊题我代码不知不觉就写长了……
这道题二分答案显然，然后用最大流\(check\)即可。设当前二分的答案为\(x\)，那么把每扇门拆成\(x\)个点，第\(i\)个代表在第\(i\)个时刻从这个门走出去。然后把每个空地往可以到达的们的相应时间连边就可以了。判一下这张图是否满流即可。
然后我们就需要先求出每个空地到门的距离……注意途中不能经过另外的门，否则会被BZOJ上加强的数据给卡掉……
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define INF 1000000000
#define maxn 200010
#define maxm 1000010
#define N 24 using namespace std;
typedef long long llg; int zx[4]={1,-1,0,0},zy[4]={0,0,-1,1};
int n,m,nu[N][N],f[N*N][N*N],dor,tol,dep[maxn],d[maxn];
int head[maxn],next[maxm],to[maxm],c[maxm],tt,S,T;
char s[N][N]; bool w[N*N]; void link(int x,int y,int z){
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
c[tt-1]=z; c[tt]=0;
} bool bfs(){
for(int i=1;i<=T;i++) dep[i]=-1;
int ld=0,rd=0; dep[d[rd++]=S]=1;
while(ld!=rd){
int u=d[ld++];
for(int i=head[u],v;v=to[i],i;i=next[i])
if(c[i] && dep[v]==-1) dep[v]=dep[u]+1,d[rd++]=v;
}
return dep[T]!=-1;
} int dfs(int u,int now){
if(!now) return 0;
if(u==T) return now;
int low=0,res;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(c[i] && dep[v]==dep[u]+1){
res=dfs(v,min(now,c[i])); low+=res;
c[i]-=res; c[i^1]+=res; now-=res;
}
if(!low) dep[u]=-1;
return low;
} bool check(int x){
tt=1; S=tol*x+1; T=S+1;
for(int i=1;i<=tol;i++)
if(w[i])
for(int j=1;j<=x;j++){
link(tol*(j-1)+i,T,1);
if(j!=x) link(tol*(j-1)+i,tol*j+i,INF);
}
else{
link(S,i,1);
for(int j=1;j<=tol;j++)
if(w[j] && f[i][j]<=x) link(i,tol*(f[i][j]-1)+j,1);
}
int now=0; while(bfs()) now+=dfs(S,INF);
for(int i=1;i<=T;i++) head[i]=0;
return now==tol-dor;
} int dx[N*N],dy[N*N]; bool vis[N][N];
void getdis(int x,int y){
int u=nu[x][y]; if(w[u]) return;
rep(i,1,n) rep(j,1,m) vis[i][j]=0;
int ld=0,rd=0; dx[rd]=x,dy[rd++]=y; vis[x][y]=1;
while(ld!=rd){
int o=dx[ld],p=dy[ld++];
for(int k=0,i,j,v;k<4;k++){
i=o+zx[k],j=p+zy[k]; v=nu[i][j];
if(i>=1 && i<=n && j>=1 && j<=m){
if(vis[i][j]) continue;
if(s[i][j]!='X') f[u][v]=f[u][nu[o][p]]+1;
if(s[i][j]=='.') dx[rd]=i,dy[rd++]=j,vis[i][j]=1;
}
}
}
} int main(){
File("a");
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++)
if(s[i][j]!='X'){
nu[i][j]=++tol;
dor+=(w[tol]=(s[i][j]=='D'));
}
}
rep(i,1,tol) rep(j,1,tol) if(i!=j) f[i][j]=INF;
rep(i,1,n) rep(j,1,m) if(nu[i][j]) getdis(i,j);
int l=0,r=tol-dor+1,mid;
while(l!=r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(l>tol-dor) printf("impossible");
else printf("%d",l);
return 0;
}