Problem H
Monster Hunter
Note: In this problem, the term mob is used as shorthand for mobile object, meaning any character or creature other than Steve, Alex, and Kai
Tired of late-night hunting trips to the forest, Alex has decided to build a mob farm to streamline the process, especially since she will soon be Away from Kai (AFK) during her next expedition.
A mob farm is a structure that assists in hunting mobs by capturing them, generally in one central location, so that players can come by periodically to clear the traps without tracking the mobs down themselves. Mob farms will also contain the captured mobs so that players do not need to worry about being shot by arrows or exploded by creepers in the process. Mob farms are frequently self-contained structures where monsters spawn in the dark interior and wander around before falling through trapdoors on the floor.
There are many different possible designs for such a farm, and Alex wants to build one that is both aesthetically pleasing and efficient! She has drafted many possible designs and has already ranked them by aesthetic. She would now like help computing their efficiencies.
Alex has meticulously analyzed the behavior of the overworld mobs, and she has determined that when a new mob spawns, it will form on a random open space in the floor plan. Every second after that, it will wander around by randomly choosing an adjacent square to move to. Mobs can either stay put or move in one of the 4 cardinal directions (but not diagonally!). They cannot move to blocks occupied by walls, and they will choose between the possible options with equal probability.
Given this information, can you compute the average number of seconds before a newly spawned mob will fall through one of the trapdoors?
![\includegraphics[width=0.45\textwidth ]{sample3.png}](/problems/monsterhunter2/file/statement/en/img-0002.png)
Sample Input 3, Minecraft 1.21.5
Input
The input begins with a line of two integers, $r$ and $c$, the number of rows and columns in the proposed floor plan.
The next $r$ lines each contain $c$ characters and depict the proposed floor plan with the following characters.
-
’O’ - a trapdoor
-
’#’ - a wall
-
’.’ - an open space
You are given that $3 \le r, c \le 12$. Additionally, there is at least one open space in the proposed plan, and all open spaces are connected to at least one trapdoor. Walls form the outer edge of the plan — after all, Alex doesn’t want creepers sneaking out into their base!
Output
Output the expected number of seconds until a newly-spawned mob falls into one of the trapdoors in the given floor plan.
Your answer will be accepted if it falls within a $10^{-5}$ absolute or relative error from the correct answer.
Explanation for Sample Input 1
In this plan, there is only a single open spot where a new mob can spawn. From that spot, there is a 50% chance to either stay put or move to the trapdoor. Because of this, it will take, on average, 2 moves (or seconds) for a mob to fall into the trapdoor.
Explanation for Sample Input 2
In this plan, there is now an additional open spot to the left of the spot in the previous test case. In the new left spot, there is a 50% chance to stay put or to move to the middle space. The middle space now has a 1/3 chance for each of the actions: stay put; move left; move right. Because of this, a mob starting in the left spot will, on average, take 7 moves to reach the trapdoor, while a mob starting in the middle will only take 5. These are averaged to produce the answer of 6.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 #### #.O# #### |
2.0000000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 ##### #..O# ##### |
6.0000000000 |
| Sample Input 3 | Sample Output 3 |
|---|---|
12 12 ############ #..........# #.###..#.#.# #......#.#.# #.###..#.#.# #....OO....# #....OO....# #.#.#..###.# #.#.#......# #.#.#..###.# #..........# ############ |
83.2075696617 |