Problem I
Ice Bucket Challenge

Obsidian, Minecraft Wiki

After collecting the diamonds, Steve is ready to go to the nether. To do this, Steve must build a rectangular portal out of obsidian, which can be obtained by pouring water on lava that he finds in caves. He has brought a water bucket with him for this purpose, and he can reuse the water in multiple caves.

When Steve places water on the ground, it begins to spread to nearby blocks. When water is first placed, it has a depth of $d$, the maximum depth of water on a block. Traditionally, this depth is 8. After that, the water begins to spread to adjacent blocks as well. As water does not flow upward, it can only spread to one of the four adjacent blocks when their height is the same or lower than the height of the current block.

When water flows to a block of the same height, its depth decreases by one (until the depth eventually reaches one and the water stops spreading). When water flows to a lower block, however, the height returns to the maximum, $d$. If water reaches a block from multiple directions with different depths, the largest depth dominates. Note that the depth of water on a block does not change when the water spreads to the surrounding blocks, so the original source block will always have a depth of $d$ until it is picked back up. (This is a slight simplification of how water actually spreads in Minecraft.)

Steve wants to know which blocks will be covered with water when he places the water bucket, so he has asked you to calculate the depth of water on each square after the water finishes spreading.

Sample 4 Solution, Minecraft 1.21.5

Input

Input begins with a line of three integers, $r$, $c$, and $d$, representing the number of rows and columns in the floor plan of the current cave, as well as the maximum depth of water. You are given that $ 1 \le r, c, d \le 1000$.

The next line has two integers $r_s$ and $c_s$, indicating the starting position where Steve places the water block. ($1 \le r_s \le r$ and $1 \le c_s \le c$)

The final $r$ lines each contain $c$ integers, $h_{i,j}$, which each represent the height of the block in the $i$th row and $j$th column. $0 \le h_{i,j} \le 20$

Output

Output a grid of $r$ rows and $c$ columns representing the depth of water on each block after the water finishes spreading.

Note that extra whitespace is ignored when grading the submission.

Explanation of Sample Input 1

This input consists of a single row of six blocks. The first five blocks have height one, while the last block has height zero. When water is placed on the first block with depth five, it begins spreading to the right while decreasing in depth. However, when the water reaches the final block with height one, it also has a depth of one. Water with a depth of one does not spread to other blocks, even when the neighboring blocks are lower. Because of this, the water never reaches the final block.

1 6 5
1 1
1 1 1 1 1 0

5 4 3 2 1 0

7 7 4
4 4
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 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 1 0 0 0
0 0 1 2 1 0 0
0 1 2 3 2 1 0
1 2 3 4 3 2 1
0 1 2 3 2 1 0
0 0 1 2 1 0 0
0 0 0 1 0 0 0

3 5 6
2 1
1 1 1 0 1
1 2 2 0 0
1 1 0 0 1

5 4 3 6 0
6 0 0 5 4
5 4 6 5 0

7 8 8
1 1
1 1 1 1 1 1 1 1
2 2 2 2 1 1 1 1
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 0 0 0 0 0
0 0 0 0 0 0 0 0

8 7 6 5 4 3 2 1
0 0 0 0 3 2 1 0
4 5 6 7 8 8 7 6
3 4 5 6 7 7 6 5
2 3 4 5 6 6 5 4
1 2 3 4 5 5 4 3
0 1 2 3 4 4 3 2