【bzoj1189】[HNOI2007]紧急疏散evacuate

2014年3月7日3,5276

 

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,得出每个点到每个门的时间

然后二分时间,每次建图dinic

S到空地连一条容量1的边,每个空地到可到达的门连一条容量1的边,每个门到T连一条容量为时间的边

 

 

 

  • xindubawukong2015年2月28日 下午4:59 回复

    您这样建图有点问题吧,似乎不能处理两个人同时在最后时刻赶到一个门的情况。
    学长能指教下吗?

    #1  
    • hzwer2015年2月28日 下午5:02 回复
      admin

      这会有什么问题么。。。

      #11
    • xindubawukong2015年2月28日 下午5:05 回复

      4 5
      XXDXX
      XX.XX
      X…X
      XXDXX
      比如这组数据,您的代码返回2,实际上答案应该是3

      #11
      • hzwer2015年2月28日 下午5:12 回复
        admin

        噢好像是这样的。。那么就对每个门按时间拆点一下吧

        #12
  • sxb_2012016年1月13日 上午9:32 回复

    学长 这个代码 被X了!!!

    #2  
    • hzwer2016年1月13日 下午8:13 回复
      admin

      是的,后来没去重写

      #21