Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
Input
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符'.'、'X'和'D'，且字符间无空格。
Output
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出'impossible'（不包括引号）。
Sample Input
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
XXXXX
X...D
XX.XX
X..XX
XXDXX
Sample Output
3
HINT
2015.1.12新加数据一组，鸣谢1756500824
C++语言请用scanf("%s",s)读入！
BFS处理出人到门的距离
二分答案，判断是否可以建边，S指向每一块空地，空地到门如果可以建边就建一条容量为x的边
每个门按照时间拆点，保证单位时间内走一次，然后跑最大流
代码太丑。。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int inf=,N=;
struct ee{int to,next,f;}e[];
struct bb{int x,y;}b[];
int head[N],q[N*],dis[N],dis1[][][],map[][];
int S,T,n,m,cnt=,ans1,w,ans,door=,num;
char s[];
int fx[]={,,,-},fy[]={,-,,};
void ins(int u,int v,int f){
e[++cnt].to=v;e[cnt].f=f;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].f=;e[cnt].next=head[v];head[v]=cnt;
} bool bfs(){
for (int i=;i<=T;i++) dis[i]=inf;
int h=,t=,now;
q[]=S;dis[S]=;
while(h!=t){
now=q[++h];
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[now]+<dis[v]){
dis[v]=dis[now]+;
if (v==T)return ;
q[++t]=v;
}
}
}
if (dis[T]==inf) return ; return ;
} int dinic(int now,int f){
if (now==T) return f;
int rest=f;
for (int i=head[now];i;i=e[i].next){
int v=e[i].to;
if (e[i].f&&dis[v]==dis[now]+&&rest){
int t=dinic(v,min(rest,e[i].f));
if (!t) dis[v]=;
e[i].f-=t;
e[i^].f+=t;
rest-=t;
//if(t) printf("%d %d %d\n",now,v,e[i].f);
}
}
return f-rest;
}
void bfs1(int k,int x1,int y1){
int h,t;h=t=;
b[++t].x=x1,b[t].y=y1;dis1[k][x1][y1]=;
while(h<t){
int x=b[++h].x,y=b[h].y;
for(int i=;i<;i++){
int nx=x+fx[i],ny=y+fy[i];
if(map[nx][ny]==&&dis1[k][nx][ny]>dis1[k][x][y]+){
dis1[k][nx][ny]=dis1[k][x][y]+;
b[++t].x=x+fx[i],b[t].y=y+fy[i];
}
}
}
} void build(int x){
memset(head,,sizeof(head));
memset(e,,sizeof(e));
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if (map[i][j]==) {
int u=(i-)*m+j;
ins(S,u,);
for(int k=;k<=door;k++)
if(dis1[k][i][j]<=x) ins(u,dis1[k][i][j]+(k-)*x+m*n,x);
}
if(map[i][j]>){
for(int k=;k<=x;k++){
int u=((map[i][j]-)*x+k)+m*n;
if(k!=x)ins(u,u+,x-k+);
ins(u,T,);
}
}
}
} bool judge(int x){
build(x);
ans=;
while(bfs())
ans+=dinic(S,inf);
if(ans>=num) return ;
return ; }
int main(){
scanf("%d%d",&n,&m);
S=,T=;
for(int i=;i<=n;i++){
scanf("%s",s+);
for(int j=;j<=m;j++) {
if (s[j]=='.')map[i][j]=,num++;
else if(s[j]=='D') map[i][j]=++door;
}
}
for(int i=;i<=door;i++)
for(int j=;j<=n;j++)
for(int k=;k<=m;k++) dis1[i][j][k]=inf;
for(int j=;j<=n;j++)
for(int k=;k<=m;k++)
if(map[j][k]>) bfs1(map[j][k],j,k);
int l=,r=;
ans1=-;
while(l<=r){
int mid=(l+r)>>;
if(judge(mid)) ans1=mid,r=mid-;
else l=mid+;
}
if(ans1==-) printf("impossible");
else printf("%d",ans1);
}