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 String[] 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: | String[], int, int | | Returns: | double | | Method signature: | double getProbability(String[] landings, int startLanding, int K) | | (be sure your method is public) |
|
| |
|
| |
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) | |
| | | Returns: 0.0 | | Note that some sections of the ride might be disconnected.
|
|
|