[HNOI2007]紧急疏散evacuate

Time Limit:10000MS  Memory Limit:165536K
Total Submit:57 Accepted:19
Case Time Limit:1000MS

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

Source

61.187.179.132:8080/JudgeOnline/showproblem
写了半天的代码，累死了。不过SAP还真是快啊。。
首先我的第一感觉是最优性改判定性，那么如何判断能否在限定时间T内将所有人转移走呢？很显然先特判一下无解的情况，首先从每个门BFS出它到每个节点的最短路，那么它最多能配上T个点且这T个点到他的最短路长度要小于T。那么就可以转化成网络流问题，从源向每个门连一条容量为T的边，从每个空地向汇连一条容量为1的边，然后不断增加T就可以了。。
就这么A掉了。可为什么这样是可以的？我感觉如果配上的T个点离的比较远的话在门上会卡住的囧，也就不可能完全利用T的时间了甚至好像可以找出反例（我没找出来）。。
也许是因为一个距离为d的点之前必然有一个距离为d-1的点之类的性质？迷茫了。。
Code(超过最大长度发不上来囧。。):
放在ideone上吧：
www.ideone.com/OdFo4hbA#