TopCoder problem "MazeWandering" used in SRM 440 (Division I Level Two)

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 a String[] 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.

Definition

Class:	MazeWandering
Method:	expectedTime
Parameters:	String[]
Returns:	double
Method signature:	double expectedTime(String[] maze)
(be sure your method is public)

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

{"*",
 "."}

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.

{"*.."}

Returns: 2.3333333333333335

The expectations for each square are 0.0, 3.0 and 4.0.

{"...",
 "X*X",
 "..."}

Returns: 4.857142857142857

{".*.",
 ".XX",
 "..."}

Returns: 13.714285714285714

{"*........",
 "XXX.XXXX.",
 ".XX.X....",
 ".....XX.X"}

Returns: 167.2608695652174

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10005

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13748&pm=10005

Writer:

gojira_tc

Testers:

PabloGilberto , ivan_metelsky , Vasyl[alphacom]

Problem categories:

Graph Theory, Math, Recursion