Chain Reaction (APCS 2024-10 Advanced)

Yi has received a treasure-hunting mission and must enter an ancient ruin to find treasure. The ruin is designed as an \(M \times N\) two-dimensional array. Each element \((r, c)\) corresponds to the cell in row \(r\) and column \(c\), where rows are numbered from top to bottom and columns from left to right, both starting from \(0\). To prevent theft, some cells contain traps, while other cells contain rocks that block signal transmission. Once a trap is triggered, it sends a signal around itself, causing traps within a certain distance to be triggered as well, which may create a chain reaction.

Each cell with a trap has a nonnegative integer representing the trap's influence radius after it is triggered. If a trap has influence radius \(x\), then traps in cells within distance \(x\) of that cell are also triggered. Distance is computed by moving one cell up, down, left, or right per step, but the path cannot enter rocks or leave the boundary. If \(x = 0\), the cell has a trap, but it does not trigger traps in other cells. Currently, except for the trap at the treasure location, all other traps have already been set. To prevent theft, the ruin designer has decided the influence radius of the trap at the treasure location, called the initial radius below. When the treasure is stolen, this trap is expected to be triggered and to trigger at least \(Q\) traps in total, including the trap at the treasure location. Write a program to compute the minimum possible initial radius at the treasure location.

For example, the ruin on the left below is a \(4 \times 5\) two-dimensional array. The cell marked \(-2\) is the treasure, cells marked \(-1\) are rocks that signals cannot pass through, and all other cells are traps whose displayed values are their influence radii. If the initial radius is \(0\), only the trap at the treasure location is triggered, so the number of triggered traps is \(1\). If the initial radius is \(1\), as shown on the right below, then \(3\) traps are triggered, and no chain reaction occurs.

If the initial radius is \(2\), then \(7\) traps are triggered at the start, as shown on the left below. Among the cells in the influence range, two traps with radius \(1\) are also triggered. These two traps newly trigger \(3\) more traps. Among them, only the trap at \((0, 4)\) has positive influence radius. Finally, that cell triggers the trap at \((1, 4)\). The chain reaction then ends, with \(11\) triggered traps in total. If the desired number of triggered traps is \(Q = 10\), the minimum initial radius is \(2\).

Input

The first line contains three integers \(M\), \(N\), and \(Q\), where \(2 \le M, N \le 500\) and \(1 < Q \le M \times N\). The next \(M\) lines each contain \(N\) integers, describing each cell from top to bottom and left to right. A value of \(-2\) denotes the treasure location. A value of \(-1\) denotes a rock. Otherwise, the value is the cell's influence radius. Each influence radius is a nonnegative integer not exceeding \(30\). In addition, \(K \le 1500\), where \(K\) is the number of cells with positive influence radius. The treasure cell appears exactly once. Adjacent values on the same line are separated by one space.

Output

Output one integer: the minimum initial radius that makes the number of triggered traps reach \(Q\). The answer is guaranteed to exist.

Sample Input 1

4 6 19
0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 -2 0 1
0 1 0 0 0 3

Sample Output 1

2

Sample Explanation 1

When the initial radius is \(2\), the triggered traps are shown below.

Sample Input 2

4 5 10
9 -1 0 1 1
1 -1 -2 -1 1
0 1 0 0 -1
0 0 0 2 0

Sample Output 2

2

Sample Explanation 2

This is the example described in the statement.

Scoring

Each test case has a time limit of \(1\) second, and Python programs have a time limit of \(4\) seconds. Scores are based on the number of test cases passed:

• Subtask 1, 20 points: \(M, N, K \le 100\), and there are no rocks.
• Subtask 2, 40 points: \(M, N \le 200\), \(K \le 500\), and all influence radii except at the treasure location are at most \(20\).
• Subtask 3, 40 points: no additional constraints.

Source

Official APCS advanced sample booklet, October 2024 programming task.