Problem Statement |
| | The king loves his queen a lot. The king wants to give a pleasant surprise to his queen and thus he wants to collect gifts for her.
You are given a String[] city which represents a rectangular grid where the j-th character in the i-th element of city is the description of the cell in row i and column j of the grid. Each cell can be of one of the following types:
- '.' - Passable cell.
- '#' - Unpassable cell.
- 'K' - The initial position of the king.
- 'Q' - The position of the queen.
- 'G' - Cell with a gift.
Note that the cells in which the king, queen and gifts are present are also passable cells.
The king can move from one cell to another if and only if both the cells are passable cells and they share a common edge (diagonal moves are not allowed). It takes the king (g+1) time units to go from a passable cell to an adjacent passable cell when the king is carrying g gifts. If the cell contains a gift then the king may collect the gift (but he doesn't have to collect it). The king does not need any additional time to collect the gift.
The king starts his trip in his initial cell. He then moves in arbitrary horizontal and vertical steps through passable cells to collect some gifts (possibly zero) and finishes the trip in the cell of the queen. The total time spent for the trip must not exceed T time units because the queen eagerly awaits the king. Return the maximum number of gifts the king can collect for the queen during such a trip. You may assume that it's always possible for the king to finish the trip within T time units. |
| |
Definition |
| | | Class: | Gifts | | Method: | maxGifts | | Parameters: | String[], int | | Returns: | int | | Method signature: | int maxGifts(String[] city, int T) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The king can visit any cell multiple times during the trip. |
| |
Constraints |
| - | city will contain between 1 and 50 elements, inclusive. |
| - | Each element of city will contain between 1 and 50 characters, inclusive. |
| - | All elements of city will have the same length. |
| - | Each character in city will be '.', '#', 'K', 'Q' or 'G'. |
| - | There will be exactly one 'K' character and one 'Q' character in city. |
| - | The number of 'G' characters in city will be between 0 and 16, inclusive. |
| - | T will be between 1 and 1000000000, inclusive. |
| |
Examples |
| 0) | |
| | {"#######",
"#K.G.Q#",
"#######"} | 6 |
| Returns: 1 | | The king collects the gift and then goes to the queen. It takes him 2 time units to reach the gift and 4 time units to reach the queen after collecting the gift (since every move takes 2 time units after he has collected the gift). Hence, the king can collect 1 gift and reach the queen in 2 + 4 = 6 time units. |
|
|
| 1) | |
| | {"#######",
"#K.G.Q#",
"#######"} | 4 |
| Returns: 0 | | The king does not have enough time to collect the gift, so he chooses not to collect the gift even though he passes through that cell. |
|
|
| 2) | |
| | {"#######",
"#K.Q.G#",
"#######"} | 6 |
| Returns: 0 | | It will take the king 4 time units to reach the gift and collect it. Then another 4 time units to reach the queen after collecting the gift. But he does not have 4 + 4 = 8 time units. Hence, he goes to the queen without any gifts. |
|
|
| 3) | |
| | {"#######",
"#K.Q.G#",
"#######"} | 8 |
| Returns: 1 | | Now the king has enough time to collect the gift and return to the queen. |
|
|
| 4) | |
| | {"#######",
"#K.QGG#",
"#######"} | 9 |
| Returns: 2 | | The king collects the gift on the left when he visits that cell for the second time. |
|
|
| 5) | |
| | {"#....G#",
"###G###",
"#K...Q#",
"###.###",
"#G..GG#"} | 50 |
| Returns: 4 | |
|