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 vector 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:vector , int
Returns:int
Method signature:int maxGifts(vector city, int T)
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
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any
unauthorized use or reproduction of this information without the prior written consent of
TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.