Maximum Euclidean Distance with Obstacle Removal

Windy has a rectangular land divided into an N × M grid of 1×1 cells. Some cells contain obstacles. Two cells, A and B, have a distance defined as the Euclidean distance between their centers, \( \sqrt{(r_A-r_B)^2+(c_A-c_B)^2} \), but only if there exists a path between them. A valid path moves between cells sharing a common edge, and a move from cell X to cell Y is allowed only if both cells are free of obstacles.

Windy is allowed to remove exactly T obstacles from the grid. After removal, the cells where obstacles have been removed become free, and a path is then defined as a sequence of adjacent free cells. It is guaranteed that after removing T obstacles at least one cell is free. Your task is to choose which obstacles to remove so that in the resulting grid, the maximum distance among any two connected cells (i.e. cells between which there is a valid path) is as large as possible. Output this maximum Euclidean distance. Note that if a pair of cells cannot be connected in the grid even after the removal, their distance is undefined and they are not considered.

Input Format: The first line contains three integers N, M and T — the number of rows, columns, and the number of obstacles Windy can remove, respectively. The next N lines each contain M space‐separated integers. Each integer is either 0 or 1, where 0 represents a free cell and 1 represents a cell with an obstacle.

Output Format: Output a single floating-point number — the maximum Euclidean distance between any two cells that can be connected after optimally removing T obstacles. Your answer is considered correct if its absolute or relative error does not exceed 10⁻⁶.

Note: When moving, if a cell initially contains an obstacle, you must count 1 against T to use that cell (including the starting and ending cells, if they initially contain an obstacle). Moves are allowed only to adjacent cells (up, down, left, right).

inputFormat

The input consists of several lines. The first line contains three integers N, M, and T. The following N lines each contain M integers (each 0 or 1) representing the grid. A value of 0 indicates a free cell, while 1 indicates an obstacle.

outputFormat

Output a single floating‐point number — the maximum Euclidean distance between any two cells that can be connected after removing at most T obstacles optimally. The result should be printed with at least 6 decimal places.

sample

2 2 0
0 0
0 0

1.4142135624