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

Construct a graph in which nodes are regions (maximal set of connected cells). Connect two regions by an edge if they share a wall. Add the outer region as a node and connect it to all regions initially exposed to water.

The solution is then obtained by running BFS on this graph, but the difficulty is to construct the graph to begin with!

Another approach is to, walk systematically around the outermost boundary, say clockwise

Pick an extreme edge

  • if there is a left edge from a vertex, take it
  • else if there is an up from a vertex, take it
  • else if there is a down edge from a vertex, take it
  • else go back

If an "external" wall has water on both sides, we will visit it twice in this traversal. Any wall we see only once will collapse. So, we maintain a count of how many times we have seen each wall as we go. Those that are visited only once will collapse in this round and can be eliminated.

We repeatedly traverse the outer wall removing walls till no more walls collapse.


Problems related to