Problem I
Parking Lot
Imagine you are walking across a parking lot of $r$ rows and $c$ columns of parking spots. All parking spots have a size of a unit square. A parking spot either is empty or contains a parked car. You can walk across an empty parking spot in any direction, but can only walk along the boundaries of a parking spot if there’s a parked car in it. You start at the top-left corner of the parking lot and walk at a constant speed of one unit distance per second. If you pick the fastest route, in how many seconds can you walk to the bottom-right corner of the parking lot?
The image illustrates two possible routes for the parking lot in the first sample case. The blue route is the fastest route in this case. The red route shows that you can walk along the boundaries of parked cars.
Input
The first line of input has two integers $r$ and $c$ ($1\leq r,c \leq 50$). The next $r$ lines each have a string of $c$ characters giving one row of parking spots from top to bottom. A dot ‘.’ indicates an empty parking spot and a hash ‘#’ indicates a parking spot with a parked car.
Output
Output the smallest amount of time in seconds you need to walk to the bottom-right corner of the parking lot. Your answer is considered correct if it has an absolute or relative error of at most $10^{-6}$ from the correct answer.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 4 ..#. .#.# ###. .#.. |
5.886349517 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 2 ## ## |
4.000000000 |
