P4162 [SCOI2009] Longest Distance

windy has a rectangular piece of land divided into $N\times M$ small $1\times 1$ cells. Some cells contain obstacles. If cell A can reach cell B, then the distance between them is defined as the Euclidean distance between their centers. If cell A cannot reach cell B, then there is no distance between them. If cells X and Y share a common edge and both X and Y contain no obstacles, you can move from X to Y. If windy can remove $T$ obstacles, find the maximum distance over all pairs of cells (considering only pairs where one can reach the other). It is guaranteed that after removing $T$ obstacles, at least one cell contains no obstacle.

The first line contains three integers, $N,M,T$. Then there are $N$ lines, each containing a string of length $M$, where `0` denotes an empty cell and `1` denotes a cell containing an obstacle.

Output a single floating-point number, with $6$ digits after the decimal point.

- For $20\%$ of the testdata, $1 \le N,M \le 30 $ and $ 0 \le T \le 0 $. - For $40\%$ of the testdata, $1 \le N,M \le 30 $ and $ 0 \le T \le 2 $. - For $100\%$ of the testdata, $1 \le N,M \le 30 $ and $ 0 \le T \le 30$. Translated by ChatGPT 5