PROBLEM STATEMENT
A new ride is opened in an amusement park. It consists of N landings numbered from 0 to N-1. Some
of the landings are connected with pipes. All of the landings are at different heights, so the
pipes are all inclined and can only be traversed downwards.A ride-taker begins his ride at some
landing. The pipes are long enough that he cannot see where they lead before entering them.
Therefore, at each landing, any descending pipe adjacent to it has an equal probability of being
used by a ride-taker who reached this landing.A ride is finished when a ride-taker reaches a
landing which has no adjacent descending pipes. There are two types of such landings: exits and
crocodile ponds. If the ride-taker reaches the exit landing, his ride is over and he safely
returns home. If one reaches the crocodile pond, his trip is also over, but he never returns
home.You're given a vector landings describing the ride. Element i of landings describes
the i-th landing. If the landing is an exit, the i-th character of landings[i] will be 'E' and the
rest of the characters will be '0's (zeroes). If it is a crocodile pond, the i-th character will
be 'P' and the rest will be '0's. If the landing has at least one adjacent descending pipe, the
j-th character of landings[i] will be '1' (one) if a pipe descends from the i-th landing to the
j-th, and '0' (zero) otherwise.A ride-taker began his ride at a randomly chosen landing, used a
total of K pipes throughout his descent and safely returned home afterwards. Each of the landings
has the same probability of being chosen as the initial landing of the ride. Compute the
probability that he started the ride at landing startLanding.
DEFINITION
Class:ParkAmusement
Method:getProbability
Parameters:vector , int, int
Returns:double
Method signature:double getProbability(vector landings, int startLanding, int K)
NOTES
-Your return value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-landings will contain exactly N elements, where N is between 2 and 50, inclusive.
-Each element of landings will contain exactly N characters.
-Each character in landings will be '0' (zero), '1' (one), 'E', or 'P'.
-If the i-th element of landings contains an 'E', it will contain only one 'E' as its i-th
character, and all other characters in that element will be '0'.
-If the i-th element of landings contains a 'P', it will contain only one 'P' as its i-th
character, and all other characters in that element will be '0'.
-If the i-th element of landings doesn't contain an 'E' or a 'P', it will contain at least one '1'
character. The i-th character of such element will always be '0'.
-K will be between 1 and N-1, inclusive.
-startLanding will be between 0 and N-1, inclusive.
-There will be no cycles in landings, i.e. it's never possible to return to the same landing after
descending through several pipes.
-There will be at least one landing from which it is possible to reach an exit using exactly K
pipes.
EXAMPLES
0)
{"E000",
"1000",
"1000",
"1000"}
1
1
Returns: 0.3333333333333333
The ride contains 4 landings, one of which is an exit. Each of the other landings has a single
pipe descending to the exit landing. Therefore, each of them could be the starting landing with
equal probability of 1/3.
1)
{"E000",
"1000",
"1001",
"000P"}
1
1
Returns: 0.6666666666666666
This time, there is an exit landing and a crocodile pond. Of the other two landings, the first has
a descending pipe only to the exit, while the second is connected both to the exit and to the
pond. So, the probability of reaching an exit starting from landing 2 is lower and the chances of
ground 1 being the start of the journey increase.
2)
{"01000100",
"00111000",
"00001010",
"000E0000",
"0000E000",
"00000P00",
"000000P0",
"01000000"}
1
2
Returns: 0.14285714285714288
Analyzing the graph above, we can see that landings 0, 1 and 7 could be the starting landings. One
can reach an exit from landing 0 using 2 pipes with probability 2/6, from landing 1 with
probability 1/6 and from landing 7 with probability 2/3. Therefore, the probability that the
ride-taker began from landing 1 is equal to (1/6)/(2/3+2/6+1/6)=1/7.
3)
{"0100",
"0010",
"0001",
"000E"}
0
2
Returns: 0.0
Obviously, the only way to get to the exit landing using 2 pipes is from ground 1. Therefore there
is no chance that landing 0 was the initial ground.
4)
{"E00",
"0E0",
"010"}
0
1
Returns: 0.0
Note that some sections of the ride might be disconnected.