MazeWandering
SRM 440 · 2009-05-12 · by gojira_tc
SRM 440 · 2009-05-12 · by gojira_tc · Graph Theory, Math, Recursion
Problem Statement
Problem Statement
According to research conducted recently, listening to classical music increases one's mental abilities, while listening to metal decreases them. Now, yet another experiment is being conducted to try to prove or disprove this statement.
In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.
One of the empty squares in the maze contains a piece of cheese, and the mouse's goal is to reach that square. The mouse can only move between neighboring empty squares. The mouse has been listening to metal for a week, so his mental abilities have become absolutely dull. Not only can he not smell the cheese, he can't even remember where he was heading a moment ago, so he is just wandering randomly. More precisely, from each square, the mouse will randomly choose one of the neighboring empty squares and move there. The probability of choosing each of the squares is equal. Each move takes one second.
You are given aString[] maze representing the maze. It contains N elements, each containing M characters. Empty squares are denoted by '.', walls are denoted by uppercase 'X', and the square containing the cheese is denoted by '*'. For each empty square, calculate the expected time required for the mouse to reach the cheese starting from that square. Return the arithmetical mean of all the expected times.
In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.
One of the empty squares in the maze contains a piece of cheese, and the mouse's goal is to reach that square. The mouse can only move between neighboring empty squares. The mouse has been listening to metal for a week, so his mental abilities have become absolutely dull. Not only can he not smell the cheese, he can't even remember where he was heading a moment ago, so he is just wandering randomly. More precisely, from each square, the mouse will randomly choose one of the neighboring empty squares and move there. The probability of choosing each of the squares is equal. Each move takes one second.
You are given a
Notes
- The returned value must have an absolute or relative error less than 1e-9.
Constraints
- maze will contain between 1 and 50 elements, inclusive.
- Each element of maze will contain between 1 and 50 characters, inclusive.
- Elements of maze will be of the same length.
- maze will contain only '.', 'X', or '*' characters.
- There will be exactly one '*' character in maze.
- For every pair of empty squares in the maze, there will exist exactly one path between them.
Examples
0)
{"*",
"."}
Returns: 0.5
The mouse will need 0 seconds to find the cheese if it is put in the cheese-square and 1 second otherwise.
1)
{"*.."}
Returns: 2.3333333333333335
The expectations for each square are 0.0, 3.0 and 4.0.
2)
{"...",
"X*X",
"..."}
Returns: 4.857142857142857
3)
{".*.",
".XX",
"..."}
Returns: 13.714285714285714
4)
{"*........",
"XXX.XXXX.",
".XX.X....",
".....XX.X"}
Returns: 167.2608695652174
Submissions are judged against all 159 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MazeWandering with a public method double expectedTime(vector<string> maze) · 159 test cases · 2 s / 256 MB per case