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:


Sample Output:


题解:


网络流什么的题目边数和点数真心不好确定,数组开大了一直编译超时找不到错误 (;′⌒`)

这个题目其实挺好写的,就是有一点难构造。
如果某个连通块中不存在门,输出Impossible
我们可以考虑二分时间,判断一个时间T是否能够让所有人出来。
对于每一扇门,我们先预先处理它到每一个空地的时间,在check时把每扇门对应每一个时间都建一个点。
若某一块空地可以在t的时间内到达这一扇门,则向t时间的这一扇门连一条边。
每一个门的节点都向汇点连一条边,源点向每一块空地连一条边。
边的大小均为1,然后若最大流等于空地数,则可以全部出去。

后来发现可以不用二分,从第一秒开始枚举,增加一秒对于每一扇门增加一个点然后连边,直到最大流等于空地数。

比二分慢一些,但还是比较块的。