Problem C
Flood Mapping

Image by klyaksun (Shutterstock); Used under license

With global warming and recurring episodes of flooding, it will be important to create flood risk maps that indicate the probability of flooding in any location. Land near a lake can be particularly vulnerable since during heavy rains a lake’s water level may rise and overflow its banks. Your challenge is to make a first attempt at creating a flood map by calculating the height of flooding (if any) at each location on a map after the lakes depicted in the map have received specified amounts of excess water.

The map of a region is a square and is divided into square cells, each of which corresponds to $1~ \textrm{square}$ metre in the real world. A cell represents either land (labelled ‘L’) or water (labelled ‘W’). A water cell is always part of a lake (i.e., we don’t consider rivers or other bodies of water). Each cell has a height in metres, meaning that all the land/water in the $1~ \textrm{square}$ metre represented by the cell has exactly that height (prior to any rain).

Note that two map cells are considered adjacent if one is directly north, south, east, or west of the other. Two cells that are northeast, southeast, northwest, or southwest of each other are not considered adjacent.

In addition to the map, you know the amount of excess water received by each lake during a heavy rain event. When water is added to a lake, the water is immediately distributed uniformly over all the lake’s cells. When the height of the water in a lake cell exceeds the height of an adjacent land cell, the water spills onto the land cell, essentially transforming it into an “adopted” lake cell, and now the height of the water is uniform over the original and adopted lake cells. This continues until no more land cells can be flooded by the lake. (If a lake cell is at exactly the same height as an adjacent land cell, the land cell is not flooded.)

Using all this information, identify the land cells that will be flooded, and give the height of the flood water on each such cell.

Additional notes:

• Lakes are probably what you might expect: Any two adjacent water cells belong to the same lake, and two non-adjacent water cells belong to the same lake if it is possible to travel from one to the other in two or more steps, where each step is a move from a water cell to an adjacent water cell.

• Water cells belonging to the same lake all have the same height, and two different lakes may or may not have different heights.

• Prior to a rain event, if a land cell and a lake cell are adjacent, the land cell is always higher.

• Water cannot move (directly) diagonally, and water cannot flow off the map. (Think of the square region depicted by a map as surrounded by infinitely high invisible walls.)

Input

The first line of input contains a positive integer, $N,$ the size of the map/region $(2 \leq N \leq 100).$ This is followed by three $N \times N$ matrices, each of which is given as $N$ lines containing $N$ space-separated characters/values. The first matrix contains only ‘L’ and ‘W’ characters, specifying the land and water cells, respectively. The second matrix gives the height, in metres, of each land or lake cell. Every height is an integer in the interval $[0, 6\, 000].$ The third matrix specifies the excess water received by each lake during a rain event. For each lake, exactly one water cell receives all the excess water for that lake (yes, we know, rain doesn’t work that way, but this is a mathematical model), and the corresponding entry in the third matrix is a positive integer no larger than $50\, 000,$ an amount of excess water in cubic metres. All other entries in the third matrix $\textrm{are}~ 0.$

To avoid some difficult cases, the input has the following guarantees:

• Two adjacent land cells will never have the same height.

• Starting from any land cell, repeatedly moving to an adjacent lower cell eventually leads to a lake.

• Water from one lake will never spill (directly or indirectly) into another lake.

• Flooding will never cause two lakes to merge together.

• The input always includes at least one land cell and at least one water cell. (After a rain event, however, it is possible that all land cells will be flooded.)

Output

Output an $N \times N$ matrix of characters/values indicating which land cells are flooded and by how much water. As in the input, this matrix should be given as $N$ lines with $N$ space-separated characters/values per line. Use ‘W’ for an original lake cell, ‘X’ for a non-flooded land cell, and a positive integer for a flooded land cell: the height of the water on that land cell, rounded up to the nearest integer.

Explanation of Sample Input/Output

The sample input has two lakes, one with $\textrm{height}~ 1$ near the top-left consisting of six cells, and one with $\textrm{height}~ 10$ in the bottom-right consisting of a single cell. The top-left lake receives $27$ cubic metres of excess water, and the small bottom-right lake receives $5$ cubic metres. For the small lake, there is no flooding for the first $4$ cubic metres as the water is rising. However, the $5^{\mathrm{th}}$ cubic metre is distributed half over the single water cell and half over the adjacent land cell to its left with $\textrm{height}~ 14$, so the land cell is flooded by $0.5~ \textrm{metres,}$ which rounds up $\textrm{to}~ 1.$ For the larger lake, the two adjacent land cells with $\textrm{height}~ 2$ are flooded with $3~ \textrm{metres}$ of water each (after rounding up), and the single adjacent land cell with $\textrm{height}~ 3$ is flooded with $2~ \textrm{metres}$ of water (after rounding up).

6
L L L L L L
L W W L L L
W W W L L L
W L L L L L
L L L L L L
L L L L L W
10 5 8 9 10 17
7 1 1 5 26 23
1 1 1 14 20 30
1 2 18 19 24 25
2 3 17 21 18 22
9 10 15 20 14 10
0 0 0 0 0 0
0 27 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 5

X X X X X X
X W W X X X
W W W X X X
W 3 X X X X
3 2 X X X X
X X X X 1 W