• 20

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## 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.|
|...|
+---+```
Output
`4.5`

A higher resolution is required to access the IDE