传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1189
思路：一种简单的网络流建图：
预处理两点间距离
从S向每个空地连1的边，每个空地向它在二分的时间内能到的出口连边，出口在向汇连T的边
这也是很多题解的做法
但这是错的...
当很多人距离门很远时，他们就可能在时间快到时堆在门口出不去，这种建图就忽略了这一点
所以我们要拆点
还是二分最大时间T，从S向每个空地连1的边
把每个门拆成T个点，表示每个时间，由每个点向汇连容量为1的边，表示每个时间只能出去一个人
然后由时间早的点向后一个时间的点连边，表示可以在门口等待到下一个时间出去
每个空地向它最早到达这个门的时间所代表的点连1的边
判断最大流是否等于空地数即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const int maxn=40010,maxm=1000010,inf=(int)1e9;
using namespace std;
int n,m,dis[510][510],map[25][25],dor[510],dcnt,blk[510],bcnt,head,tail;char ch[25][25];bool bo[25][25];
int pre[maxm],now[maxn],son[maxm],val[maxm],tot,di[maxn],S=maxn-2,T=maxn-1,maxt=80;
struct poi{int x,y;}q[510];
int id(int x,int y){return (x-1)*m+y;}
void bfs(int sx,int sy){
int st=id(sx,sy);
memset(dis[st],63,sizeof(dis[st]));
memset(bo,0,sizeof(bo));
q[tail=1]=(poi){sx,sy};
head=0,dis[st][st]=0,bo[sx][sy]=1;
while (head!=tail){
if (++head>500) head=1;
poi a=q[head];
for (int i=0;i<4;i++){
int nx=a.x+dx[i],ny=a.y+dy[i];
if (bo[nx][ny]) continue;
if (map[nx][ny]==1){
if (++tail>500) tail=1;
bo[nx][ny]=1,dis[st][id(nx,ny)]=dis[st][id(a.x,a.y)]+1;
q[tail]=(poi){nx,ny};
}
else if (map[nx][ny]==2)
bo[nx][ny]=1,dis[st][id(nx,ny)]=dis[st][id(a.x,a.y)]+1;
}
}
}
void init(){
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (map[i][j]==1) bfs(i,j),blk[++bcnt]=id(i,j);
else if (map[i][j]==2) dor[++dcnt]=id(i,j);
}
struct Tflow{
int q[maxn+10],head,tail;
int id(int x,int tim){return (x-1)*maxt+tim+bcnt;}
void add(int a,int b,int c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
void ins(int a,int b,int c){add(a,b,c),add(b,a,0);}
void clear(){memset(now,0,sizeof(now)),tot=1;}
bool bfs(){
memset(di,-1,sizeof(di));
q[1]=S,di[S]=0,head=0,tail=1;
while (head!=tail){
if (++head>maxm) head=1;
int x=q[head];
for (int y=now[x];y;y=pre[y])
if (di[son[y]]==-1&&val[y]){
if (++tail>maxm) tail=1;
di[son[y]]=di[x]+1,q[tail]=son[y];
}
}
return di[T]>0;
}
int find(int x,int low){
if (x==T) return low;
int y,res=0;
for (y=now[x];y;y=pre[y]){
if (!val[y]||di[son[y]]!=di[x]+1) continue;
int tmp=find(son[y],min(low,val[y]));
val[y]-=tmp,val[y^1]+=tmp,res+=tmp,low-=tmp;
if (!low) break;
}
if (!y) di[x]=-1;
return res;
}
bool dinic(int lim){
int res=0;clear();
for (int i=1;i<=bcnt;i++) ins(S,i,1);
for (int i=1;i<=dcnt;i++) for (int j=1;j<=lim;j++){
ins(id(i,j),T,1);
if (j>1) ins(id(i,j-1),id(i,j),inf);
}
for (int i=1;i<=bcnt;i++)
for (int j=1;j<=dcnt;j++){
int x=blk[i],y=dor[j];
if (dis[x][y]<=lim) ins(i,id(j,dis[x][y]),1);
}
while (bfs()) res+=find(S,inf);
return res==bcnt;
}
}Ts;
void work(){
int l=1,r=n*m,mid=(l+r)>>1,ans=-1;
while (l<=r){
if (Ts.dinic(mid)) r=mid-1,ans=mid;
else l=mid+1;
mid=(l+r)>>1;
}
if (ans==-1) puts("impossible");
else printf("%d
",ans);
}
int main(){
scanf("%d%d",&n,&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') map[i][j]=2;
else if (ch[i][j]=='.') map[i][j]=1;
init(),work();
return 0;
}