Goal
An ant leaves its anthill in order to forage for food, but it doesn't know where to go, therefore every second it moves randomly step cm directly north, south, east or west with equal probability.
You will work with an ascii representation of the anthill, where the initial position of the ant is represented by the letter A, and the borders of the anthill by the characters |, - and + for the corners. The distance between each element of the anthill is equal to 1 cm. In this version, the anthill is always a RECTANGLE.
If the food is located at the borders of the anthill, how long will it take the ant to reach it on average (rounded to 1 decimal place)?
NOTE: The ant reaches its food if it ends on the border of the anthill OR outside the anthill.
The original problem can be found here: https://web.archive.org/web/20220817071104/https://optiver.com/working-at-optiver/career-opportunities/5841549002/
Input
Line 1: An integer step.
Line 2: Two space-separated integers w and h: the width and height of the ascii anthill.
Next h lines: w characters representing the h-th row of the ascii anthill.
Output
The average time (in seconds) it takes the ant to reach its food (a float rounded to 1 decimal place).
Constraints
1 <= step <= 3
3 <= w, h <= 15
The ant always starts INSIDE the anthill (never at the borders or outside).
Example
Input
1
5 5
+---+
|...|
|.A.|
|...|
+---+
