Flooding a landscape
Given a description of a landscape, describe how it will be flooded by the water.
Problem statement
You are given a rectangular grid. Grid cells represent squares of a landscape. Some of the segments adjacent to two grid cells can contain a wall. Now at time zero water is flooding from the border, stopping at walls. At time 1, these walls break and water continues to flood the landscape. At time 2, again walls at the border of the water break. Eventually all grid cells are flooded. At this point your goal is output the list of all walls which are still standing.
Reduction to a shortest path problem
When you see the word “flood”, you might think that this is a flow problem. But it can be reduced to a simple shortest path problem. Suppose we compute for every grid cell c, the time it will be flooded. Denote this value by flood[c]. Then every wall between two cells c and d breaks if flood[c] != flood[d], and still stands otherwise.
Consider a graph, where every grid cell is a vertex, and there is an additional vertex, represeting the water source. Connect the source to all border cells with a zero weighted edge. Connect vertices corresponding to adjacent grid cells, and weight the edge by 1 if there is a wall between them, and by 0 otherwise.
Compute the shortest path distance from the source to every grid cell. Since the graph is {0,1}-weighted, this can be done using a double-ended queue, as implemented here. In a few words: When running Dijkstra’s shortest path algorithm on a {0,1}-weighted graph, the priority queue of still to be visited vertices, contains only two kind of priorities, namely k and k+1, for some value k (which changes over time). Hence the priority queue can be simply represented by a double ended queue. When processing a vertex v at distance k from the source, then we add all its unvisited neighbors to the queue: and add them to the beginning of the queue of they are reached with a 0 valued edge (priority k) and to the end if they are reached with a 1 valued edge (priority k+1). Doing this, the elements of the queue will always be ordered by their priority.
Complexity
The complexity is linear in the grid size.