Problem Statement |
| | A city is square and is laid out in nice regular blocks, except that there is one block that
has a "shortcut", a narrow road that goes diagonally through the block. The bank has
just been robbed, and our one on-duty police car starts to chase down the robbers.
The police and robbers always drive at top speed, and they have exactly the same
top speed. Neither the police nor the robbers can leave the city.
It takes 10 seconds to drive one block. It also takes 10 seconds to drive the
shortcut. The police have one advantage -- they have a "bug" in the robbers' car.
One of the robbers tells the driver which way to turn just before they reach each intersection, so
the police can choose their next turn appropriately.
The robbers are apprehended when the police and robbers are at
the same intersection at the same time or when a head-on collision occurs on
the shortcut. (The regular roads are divided roads, so the police cannot apprehend
the robbers if they pass each other going in opposite directions.) U-turns at intersections are
possible, but neither the police nor the robbers may slow down or stop.
Create a class Robbery that contains the method apprehend that takes
the width of the city, n, and a int[] map, giving the locations of the
shortcut, robbers and police as inputs and returns the amount of time until
the robbers are apprehended. If the police can never apprehend the robbers,
the method should return -1. Assume that both the police and robbers behave
optimally (other than robbing the bank in the first place).
n is the number of blocks in both directions (since the city is square). The
intersections are located at x,y where x and y are between 0 and n inclusive.
map contains exactly 8 values: shortcutX1,shortcutY1,shortcutX2,shortcutY2,
policeX,policeY,robbersX,robbersY.
|
| |
Definition |
| | | Class: | Robbery | | Method: | apprehend | | Parameters: | int, int[] | | Returns: | int | | Method signature: | int apprehend(int n, int[] map) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | n is between 2 and 30 inclusive. |
| - | map contains exactly 8 elements. |
| - | Each element in map is between 0 and n inclusive. |
| - | The absolute value of (shortcutX1 - shortcutX2) is 1. |
| - | The absolute value of (shortcutY1 - shortcutY2) is 1. |
| - | map specifies distinct locations for the police and robbers. |
| |
Examples |
| 0) | |
| | | Returns: 30 |
*---*---*---*
| | | |
*---*---*---*
| / | | |
*---P---*---R
| | | |
*---*---*---*
(All example diagrams have (0,0) in the lower left corner.)
If the robbers go west, the police will go east apprehending in 1*10 seconds.
If the robbers go south, the police will go east. Then the robbers will have
to go north or west and will be apprehended after 2*10 = 20 seconds.
If the robbers go north, they will be trapped when they get to the northeast
corner of the city, and will be apprehended after 30 seconds.
|
|
|
| 1) | |
| | | Returns: 50 |
*---*---*---*
| | | |
*---*---*---*
| / | | |
*---P---R---*
| | | |
*---*---*---*
The best strategy for the police is to go west, then northeast (using the
shortcut). The robbers can do no better than to head
north, then east, then south and south. Even so, they will then be trapped in
the southeast corner of the city and will be apprehended 10 seconds later.
|
|
|
| 2) | |
| | | Returns: 50 |
*---*---*---*
| | | |
*---R---P---*
| | \ | |
*---*---*---*
| | | |
*---*---*---*
|
|
|
| 3) | |
| | | Returns: 70 |
*---*---*---*
| | | |
*---*---*---*
| | | |
*---*---*---*
| \ | | |
*---R---*---P
|
|
|
| 4) | |
| | | Returns: 60 |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
| | \ | | | |
R---P---*---*---*---*
| | | | | |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
|
|
|
| 5) | |
| | | Returns: 90 |
P---*---*---*---*---*
| | | | | |
R---*---*---*---*---*
| | \ | | | |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
| | | | | |
*---*---*---*---*---*
|
|
|