Problem Statement |
| | You're trapped inside a facility that contains several rooms connected by corridors. You're currently located in room start and you wish to reach the finish using the least amount of time as possible. Each corridor takes one second to travel through.
Your task is complicated by the fact that there are several agents located in various rooms. These agents wish to capture you, but each one has a particular destination, as they each have different intelligence suggesting that you will head towards their destination. Like yourself, these agents will also reach their target room in the least possible amount of time. The agents begin moving at the same time as you do. If there are multiple shortest paths that an agent may use, you may assume each such path is equally likely as his choice. Once an agent reaches his goal, he will stay there indefinitely. Note that while you are aware of each agent's start and target rooms, you will be unaware of the agent's movements as you move through the facility.
As you wish to dodge capture as well as reach the exit as quickly as possible, you will use the following strategy.
Each second you choose the way which allows you to reach the exit as quickly as possible (see example 6 for clarification). If there are multiple ways to do so, you choose the corridor that minimizes the probability of being captured from that point on. As soon as you reach the exit room, you leave the facility and cannot be captured. However, you may be captured the moment that you reach the exit room (see example 7).
There are two ways that you can be captured by an agent.
1) You travel through a corridor at the same time an agent does (you can be traversing the corridor in either the same direction or the opposite direction).
2) You're in a room at the same time as an agent.
The facility is described by a String[] corridors. The jth character of the ith element of corridors will be a '1' if there is a corridor between rooms i and j, and '0' otherwise. Each element of agentStart and agentTarget represents the start and target rooms, respectively, of an agent.
Given this information, return the probability that you will be captured by an agent if you follow the described strategy.
|
| |
Definition |
| | | Class: | EscapeArtist | | Method: | bestRoute | | Parameters: | String[], int[], int[], int, int | | Returns: | double | | Method signature: | double bestRoute(String[] corridors, int[] agentStart, int[] agentTarget, int start, int finish) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The returned value must be accurate to within a relative or absolute value of 1E-9. |
| |
Constraints |
| - | corridors will contain between 2 and 25 elements, inclusive. |
| - | Each element of corridors will contain exactly N characters, where N is the number of elements in corridors. |
| - | Each character in corridors will be either a '0' (zero) or '1' (one). |
| - | The jth character of the ith element of corridors will be the same as the ith character of the jth element of corridors. |
| - | The ith character of the ith element of corridors will be '0'. |
| - | start and finish will each be between 0 and N-1, inclusive, where N is the number of elements in corridors. |
| - | start will be different from finish. |
| - | agentStart and agentTarget will each contain between 1 and 10 elements, inclusive. |
| - | agentStart and agentTarget will contain the same number of elements. |
| - | Each agent's starting room will be different from his target room. |
| - | No agent will start in the same room as you. |
| - | Each element of agentStart and agentTarget will be between 0 and N-1, inclusive, where N is the number of elements in corridors. |
| - | There will be at least one path between each pair of rooms in the facility. |
| |
Examples |
| 0) | |
| | {
"0100",
"1011",
"0100",
"0100"
} | {3} | {1} | 0 | 2 |
| Returns: 1.0 | 3
|
|
0---1---2
The agent will always arrive at room 1 at the same time as you do, so there is no way to avoid capture. |
|
|
| 1) | |
| | {
"01000",
"10110",
"01000",
"01001",
"00010"
} | {4} | {1} | 0 | 2 |
| Returns: 0.0 | 2
|
|
0---1---3---4
You will reach room 1 before the agent does, so you will avoid capture. |
|
|
| 2) | |
| | {
"010000",
"101011",
"010111",
"001000",
"011000",
"011000"
} | {4} | {5} | 0 | 3 |
| Returns: 0.5 | 4
/ \
0--1---2--3
\ /
5
Your path must be 0-1-2-3. The agent is equally likely to take the paths 4-1-5 or 4-2-5. If he takes the first path, you will be captured in room 1. However, if he takes the second path, you will escape. |
|
|
| 3) | |
| | {
"010000",
"101001",
"010110",
"001000",
"001000",
"010000"
} | {4} | {5} | 0 | 3 |
| Returns: 1.0 | 5 4
| |
| |
0---1---2---3
You will be travelling through the corridor between rooms 1 and 2 at the same time the agent travels through the same corridor in the opposite direction. |
|
|
| 4) | |
| | {
"01100",
"10011",
"10010",
"01100",
"01000"
} | {4,3} | {1,0} | 0 | 3 |
| Returns: 0.5 | 0
/ \
4---1 2
\ /
3
Here you can choose between two paths. If you take path 0-1-3, you will always be captured by the first agent at room 1. However, if you take path 0-2-3, there is a 50% chance that you will be captured in room 2, depending on which path the second agent takes. |
|
|
| 5) | |
| | {
"0100",
"1010",
"0101",
"0010"
} | {3} | {2} | 0 | 3 |
| Returns: 1.0 | 0--1--2--3
The agent reaches room 2 before you, but stays there indefinitely. You will then be captured as soon as you enter room 2. |
|
|
| 6) | |
| | {"0101", "1010", "0101", "1010"} | {1} | {0} | 0 | 1 |
| Returns: 1.0 |
0 -- 1
| |
| |
3----2
The longer path (0 -> 3 -> 2 -> 1) is absolutely safe, but you must take the shortest one (0 --> 1). |
|
|
| 7) | |
| | {"011", "101", "110"} | {0} | {1} | 2 | 1 |
| Returns: 1.0 | | You are caught at the moment you enter room 1. |
|
|