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
Sample Output
3解题思路：考虑每个点到每个门的最短路一定所以先Bfs/Dijstra一遍得到每个点到每个门到最短距离。考虑随着时间的推移，每个点能够到达的门也就越多，所以可以说是动态加边。这时的正确方法是二分答案，建图网络流。显然是源点连人，在时间允许的情况下人连门，容量为1。门连汇点，容量为T。这样做理论上是很好的，但是有一个问题，那就是本题的特殊性，每个格子可以重复走人但是门只能一个一个出。这就十分不和谐了，因为上面的做法并不能处理两个人同时到达的情况。考虑一个问题，到底是什么性质没有被体现导致建图瑕疵。这里可以认为门在T时刻关闭，那么本质上每个人都有一个剩余时间，假如说一起到然后一个一个出，这里的问题就是假如说一起到的人比较多，假如说大于T那么一定不能全部出去。所以需要有一个条件来限制每个人到达时还剩多少时间，换句话说，需要表现他究竟是什么时间到达的。这样，将每个门拆成T个点，代表该时刻到达的门（相当于给门分层）。每个点向到达时间的门连边，每层门向下一层连流量为$inf$的边。跑最大流验证就好了。代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int oo=0x3f3f3f3f;
struct int_2{int TIME;int NO;};
struct pnt{
int hd;
int lyr;
int now;
}p[];
struct ent{
int twd;
int vls;
int lst;
int his;
}e[];
struct OVO{
int_2 pro;
int i;
int j;
};
int cnt;
int n,m;
int s,t;
int pnum;
char tmp[];
int no[][];
int mp[][];
bool vis[][];
bool hvv[][];
std::queue<int>Q;
std::queue<OVO>P;
std::vector<int>T[];
std::vector<int_2>dr[][];
void ade(int f,int t,int v)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].his=v;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
bool bfs(void)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(mp[i][j]==)
{
while(!P.empty())
P.pop();
P.push((OVO){(int_2){,no[i][j]},i,j});
while(!P.empty())
{
OVO x=P.front();
P.pop();
int ii=x.i;
int jj=x.j;
if(vis[ii][jj])
continue;
vis[ii][jj]=true;
if(mp[ii][jj]==)
dr[ii][jj].push_back(x.pro);
x.pro.TIME++;
OVO y;
y=x;
y.i++;
if(y.i<=n)
{
if(mp[y.i][y.j]==)
{
P.push(y);
}
}
y=x;
y.i--;
if(y.i>)
{
if(mp[y.i][y.j]==)
{
P.push(y);
}
}
y=x;
y.j++;
if(y.j<=m)
{
if(mp[y.i][y.j]==)
{
P.push(y);
}
}
y=x;
y.j--;
if(y.j>)
{
if(mp[y.i][y.j]==)
{
P.push(y);
}
}
}
for(int ii=;ii<=n;ii++)
{
for(int jj=;jj<=m;jj++)
{
if(vis[ii][jj])
hvv[ii][jj]=true;
vis[ii][jj]=false;
}
}
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(!hvv[i][j]&&mp[i][j]==)
return true;
}
}
return false;
}
bool Bfs(void)
{
while(!Q.empty())Q.pop();
for(int i=;i<=t;i++)
p[i].lyr=;
p[s].lyr=;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==&&e[i].vls>)
{
p[to].lyr=p[x].lyr+;
if(to==t)
return true;
Q.push(to);
}
}
}
return false;
}
int Dfs(int x,int fll)
{
if(x==t)
return fll;
for(int& i=p[x].now;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==p[x].lyr+&&e[i].vls>)
{
int ans=Dfs(to,std::min(fll,e[i].vls));
if(ans>)
{
e[i].vls-=ans;
e[((i-)^)+].vls+=ans;
return ans;
}
}
}
return ;
}
int Dinic(void)
{
int ans=;
while(Bfs())
{
for(int i=;i<=t;i++)
p[i].now=p[i].hd;
int dlt;
while(dlt=Dfs(s,oo))
ans+=dlt;
}
return ans;
}
bool Check(int x)
{
for(int i=;i<=t;i++)
p[i].hd=;
cnt=;
int lcnt=n*m;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(mp[i][j]==)
{
T[no[i][j]].clear();
for(int k=;k<=x;k++)
T[no[i][j]].push_back(++lcnt);
}
s=lcnt+;
t=s+;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(mp[i][j]==)
{
ade(s,no[i][j],);
ade(no[i][j],s,);
for(int k=;k<dr[i][j].size();k++)
{
if(dr[i][j][k].TIME<=x)
{
ade(no[i][j],T[dr[i][j][k].NO][dr[i][j][k].TIME],);
ade(T[dr[i][j][k].NO][dr[i][j][k].TIME],no[i][j],);
}
}
}else if(mp[i][j]==)
{
for(int k=;k<=x;k++)
{
ade(T[no[i][j]][k],t,);
ade(t,T[no[i][j]][k],);
if(k!=x)
{
ade(T[no[i][j]][k],T[no[i][j]][k+],oo);
ade(T[no[i][j]][k+],T[no[i][j]][k],);
}
}
}
}
}
return pnum==Dinic();
}
int main()
{
// freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%s",tmp+);
for(int j=;j<=m;j++)
{
no[i][j]=++cnt;
if(tmp[j]=='X')
mp[i][j]=;
if(tmp[j]=='.')
mp[i][j]=,
pnum++;
if(tmp[j]=='D')
mp[i][j]=;
}
}
cnt=;
if(bfs())
{
puts("impossible");
return ;
}
int l=,r=;
int ans;
while(l<=r)
{
int mid=(l+r)>>;
if(Check(mid))
{
ans=mid;
r=mid-;
}else
l=mid+;
}
printf("%d\n",ans);
return ;
}
