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
Solution
$Update$：写假了，先别看了QwQ
这个题……有点像跳舞那个题emmmm……
答案肯定是满足单调性的，所以我们可以枚举
（可以和跳舞那个题一样二分，不过二分就要每次重新添加边，太麻烦）
先判断impossible，BFS判断就行。
建图：超级源点-人-门-超级汇点
枚举秒数，每一秒就在门和超级汇点间连一条容量1的边，意味着当前秒这个门可以多出一个人了
若某个人到某个门耗费的时间为当前秒数，就在人和门间连一条容量为1的边
之后跑一边最大流，若最大流为人数的话就说明人可以全跑出去了
PS每次跑最大流的时候之前的Ans不能清零emmm
答案肯定是满足单调性的，所以我们可以枚举
（可以和跳舞那个题一样二分，不过二分就要每次重新添加边，太麻烦）
先判断impossible，BFS判断就行。
建图：超级源点-人-门-超级汇点
枚举秒数，每一秒就在门和超级汇点间连一条容量1的边，意味着当前秒这个门可以多出一个人了
若某个人到某个门耗费的时间为当前秒数，就在人和门间连一条容量为1的边
之后跑一边最大流，若最大流为人数的话就说明人可以全跑出去了
PS每次跑最大流的时候之前的Ans不能清零emmm
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define MAXM (100000+10)
#define MAXN (1010+10)
using namespace std;
struct node
{
int Flow;
int next;
int to;
}edge[MAXM*];
int Depth[MAXN],Q[MAXN];
int head[MAXN],num_edge;
int n,m,s,e=,d,INF;
int a[MAXN][MAXN];
int num[MAXN][MAXN];
int dis[MAXN][MAXN];
int PEOPLE[MAXN],P_sum;
int DOOR[MAXN],D_sum;
int dx[]={,,-,,},dy[]={,,,,-};
int q[][];
int Ans;
bool used[][];
char ch[]; void add(int u,int v,int l)
{
edge[++num_edge].to=v;
edge[num_edge].Flow=l;
edge[num_edge].next=head[u];
head[u]=num_edge;
} bool Bfs(int s,int e)
{
int Head=,Tail=;
memset(Depth,,sizeof(Depth));
Depth[s]=;
Q[]=s;
while (Head<Tail)
{
int x=Q[++Head];
for (int i=head[x];i!=;i=edge[i].next)
if (!Depth[edge[i].to] && edge[i].Flow>)
{
Depth[edge[i].to]=Depth[x]+;
Q[++Tail]=edge[i].to;
}
}
if (Depth[e]>) return true;
return false;
} int Dfs(int x,int low)
{
int Min,f=;
if (x==e || low==)
return low;
for (int i=head[x];i!=;i=edge[i].next)
if (edge[i].Flow> && Depth[edge[i].to]==Depth[x]+ && (Min=Dfs(edge[i].to , min(low,edge[i].Flow) )))
{
edge[i].Flow-=Min;
edge[((i-)^)+].Flow+=Min;
f+=Min;
low-=Min;
}
return f;
} int Dinic(int s,int e)
{
// int Ans=0;
while (Bfs(s,e))
Ans+=Dfs(s,0x7fffffff);
return Ans;
} void DISTANCE(int x,int y)
{
int Head=,Tail=;
memset(used,false,sizeof(used));
q[][]=x;
q[][]=y;
used[x][y]=true;
while (Head<Tail)
{
++Head;
for (int i=;i<=;++i)
{
int xx=q[Head][]+dx[i];
int yy=q[Head][]+dy[i];
if (!used[xx][yy] && a[xx][yy])
{
used[xx][yy]=true;
dis[num[x][y]][num[xx][yy]]=dis[num[x][y]][num[q[Head][]][q[Head][]]]+;
q[++Tail][]=xx;
q[Tail][]=yy;
}
}
}
} int main()
{
memset(&INF,0x7f,sizeof(INF));
int n,m,cnt=;
scanf("%d%d",&n,&m);
for (int i=;i<=n;++i)
{
scanf("%s",ch);
for (int j=;j<=m;++j)
{
if (ch[j-]=='X')
continue;
num[i][j]=++cnt;
if (ch[j-]=='.')
{
a[i][j]=;
PEOPLE[++P_sum]=num[i][j];
}
else
{
a[i][j]=;
DOOR[++D_sum]=num[i][j];
}
}
}
for (int i=;i<=n;++i)
for (int j=;j<=m;++j)
if (a[i][j])
DISTANCE(i,j);
for (int i=;i<=P_sum;++i)
{
bool flag=false;
for (int j=;j<=D_sum;++j)
if (dis[PEOPLE[i]][DOOR[j]]!=)
{
flag=true;
break;
}
if (!flag)
{
printf("impossible\n");
return ;
}
}
for (int i=;i<=P_sum;++i)
{
add(,PEOPLE[i],);
add(PEOPLE[i],,);
}
for (int i=;i<=;++i)
{
for (int j=;j<=D_sum;++j)
{
add(DOOR[j],,);
add(,DOOR[j],);
}
for (int j=;j<=P_sum;++j)
for (int k=;k<=D_sum;++k)
if (dis[PEOPLE[j]][DOOR[k]]==i)
{
add(PEOPLE[j],DOOR[k],);
add(DOOR[k],PEOPLE[j],);
}
if (Dinic(,)==P_sum)
{
printf("%d",i);
return ;
}
}
}