32055번 - Storing Eggs 스페셜 저지다국어

You have an egg carton that can be represented as a $3 \times N$ grid. The grid consists of $3$ rows, numbered from $1$ to $3$, and $N$ columns, numbered from $1$ to $N$. The cell at row $r$ and column $c$ is denoted as $(r, c)$. Each cell can be either usable or unusable; each usable cell can only hold at most $1$ egg while unusable cells, as the name implies, cannot be used.

You want to put exactly $K$ eggs into usable cells of your carton such that the distance between any two closest eggs is maximized. The distance between an egg in cell $(r_1, c_1)$ and another egg in cell $(r_2, c_2)$ can be calculated using Euclidean distance, i.e. $\sqrt{(r_1-r_2)^2 + (c_1-c_2)^2}$.

Determine the maximum possible distance between any two closest eggs, or determine if it is impossible to put $K$ eggs into your carton.

Input begins with two integers $N$ $K$ ($1 ≤ N ≤ 100$; $2 ≤ K ≤ 3N$) representing the number of columns of your egg carton and the number of eggs. Each of the next $3$ lines contains a string $S_r$ of length $N$ that consists of either character ‘.’ or ‘#’. The c^th character of string $S_r$ represents the condition of cell $(r, c)$ of the carton. Cell $(r, c)$ is usable if $S_{r,c} =$ ‘.’ and unusable if $S_{r,c} =$ ‘#’.

If $K$ eggs can be put into your carton, then output a real number in a single line representing the maximum possible distance between any two closest eggs. Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

If $K$ eggs cannot be put into your carton, then output -1 in a single line.