The famous spy, Cute Noodle Hawk(C-N-Hawk), is facing a dangerous mission. C-N-Hawk steals significant intelligence from the enemy. While leaving the dangerous area, he find problems. The area to the south of Hawk is dangerous, which is full of mines.
Hawk will tell you the size of the dangerous area with two integers M
(1 ≤ M
≤ 50). Then he will draw a map of M
blocks with '.' or '@'. A block with '.' means it is safe and '@' means there is a mine in it. The dangerous area contains at least one mine. There are several test cases in the input, and the input will end with M
C-N-Hawk can enter the dangerous area by moving to any block on the north edge and leave it by exiting from any block on the south edge. In the area, C-N-Hawk can move from the current block to an adjacent block. That means he can move in one of the four directions: north, east, south or west. Moving in diagonal is impossible.
C-N-Hawk should keep himself from the mines as far as possible. Please find a path to help him to arrive the south and make the path from the mines farthest.
The B-distance of a block is defined as the distance between the block and the nearest mine. It is calculate as Euclid Distance. For example, if the block (x1, y1) has the nearest mine in block (x2, y2), the distance is sqrt((x1-x2)2
). The P-distance of a path is defined as the smallest B-distance on the path.
Please output the maximum P-distance for each cases, rounded to four decimal places. If C-N-Hawk can not arrive the south, the P-distance is consider as zero (0.0000).
The best path for the case is: (1,3)→(2,3)→(2,4)→(3,4)→(4,4).
Both the blocks (2,3) and (2,4) have the smallest B-distance 1.4142, so the P-distance is 1.4142.