Indian Computing Olympiad

Training Material

Advanced Graph Algorithms→Flood (IOI 2007)

In 1964 a catastrophic flood struck the city of Zagreb. Many buildings were completely destroyed when the water struck their walls. In this task, you are given a simplified model of the city before the flood and you should determine which of the walls are left intact after the flood.

The model consists of N points in the coordinate plane and W walls. Each wall connects a pair of points and does not go through any other points. The model has the following additional properties:

  • No two walls intersect or overlap, but they may touch at endpoints;
  • Each wall is parallel to either the horizontal or the vertical coordinate axis.

Initially, the entire coordinate plane is dry. At time zero, water instantly floods the exterior (the space not bounded by walls). After exactly one hour, every wall with water on one side and air on the other breaks under the pressure of water. Water then floods the new area not bounded by any standing walls. Now, there may be new walls having water on one side and air on the other. After another hour, these walls also break down and water floods further. This procedure repeats until water has flooded the entire area.

An example of the process is shown in the following figure. 

--------------------  --------------------  --------------------
-OooooooOoooooooooO-  -O------O---------O-  -O------O---------O-
-o      o         o-  --------o-----------  --------o-----------
-o      OooooooO  o-  --------OooooooO----  --------O------O----
-o      o      o  o-  --------o      o----  --------o-----------
-o  OoooOoooO  o  o-  ----OoooOoooO  o----  --------OoooO-------
-o  o       o  o  o-  ----o       o  o----  ----------- o-------
-o  OoooOoooO  o  o-  ----OoooOoooO  o----  ----OoooOoooO-------
-o      o      o  o-  --------o      o----  --------------------
-o      OooooooO  o-  --------OooooooO----  --------O------O----
-o                o-  --------------------  --------------------
-O oooooooooooooooO-  -O----------------O-  -O----------------O-
--------------------  --------------------  --------------------
    Time zero            After one hour        After two hours
                                              All areas flooded
                                               4 walls remain

Solution


Problems related to