Markov ants
Statement
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
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:
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.
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).
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
Tags
Random walk, Markov chains, Probability, Simulation
Difficulty
Medium
Test cases
Base case Test
Input
1
5 5
+---+
|...|
|.A.|
|...|
+---+
Output
4.5
Base case idem Validator
Input
1
5 5
+---+
|...|
|.A.|
|...|
+---+
Output
4.5
Square 6 Test
Input
1
7 7
+-----+
|.....|
|.....|
|..A..|
|.....|
|.....|
+-----+
Output
10.4
Square 8 Validator
Input
1
9 9
+-------+
|.......|
|.......|
|.......|
|...A...|
|.......|
|.......|
|.......|
+-------+
Output
18.6
Different step Test
Input
3
7 7
+-----+
|.....|
|.....|
|..A..|
|.....|
|.....|
+-----+
Output
1.0
Different step val Validator
Input
2
7 7
+-----+
|.....|
|.....|
|..A..|
|.....|
|.....|
+-----+
Output
4.5
Different origin Test
Input
1
5 5
+---+
|...|
|..A|
|...|
+---+
Output
3.5
Different origin val Validator
Input
1
7 7
+-----+
|.....|
|.A...|
|.....|
|.....|
|.....|
+-----+
Output
8.5
Different shape (rectangle) Test
Input
1
5 3
+---+
|.A.|
+---+
Output
1.7
Different shape (rectangle) val Validator
Input
1
9 5
+-------+
|.......|
|...A...|
|.......|
+-------+
Output
7.2
Different shape + start Test
Input
1
9 5
+-------+
|.......|
|....A..|
|.......|
+-------+
Output
6.9
Different shape + start Validator
Input
1
9 5
+-------+
|.......|
|.......|
|.A.....|
+-------+
Output
4.6
Different shape + start + step Test
Input
2
9 5
+-------+
|.......|
|....A..|
|.......|
+-------+
Output
1.8
Different shape + start + step Validator
Input
3
9 5
+-------+
|.......|
|.......|
|....A..|
+-------+
Output
1.3
Extra test 1 Test
Input
2
12 8
+----------+
|..........|
|....A.....|
|..........|
|..........|
|..........|
|..........|
+----------+
Output
4.8
Extra val 1 Validator
Input
2
12 8
+----------+
|..........|
|..........|
|..........|
|..........|
|.......A..|
|..........|
+----------+
Output
4.4
Extra test 2 Test
Input
2
15 15
+-------------+
|.............|
|....A........|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
+-------------+
Output
8.0
Extra val 2 Validator
Input
2
15 15
+-------------+
|.............|
|.............|
|.............|
|.............|
|.............|
|........A....|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
|.............|
+-------------+
Output
15.0
Solution language
Solution
Stub generator input