Problem H
Robot Delivery
What a busy day! Tyko has been diligently preparing problems for an upcoming programming contest all day. He has been so busy that he forgot to eat lunch and now he is quite hungry! "What if I made some sort of robot-based food delivery system?" he thinks to himself. Of course the system would have to be optimized so that the maximum time any robot has to travel is minimized. Furthermore, each robot should only deliver food to one person to prevent people from stealing other peoples food.
The area on which the robots will travel can be described by a grid, on which the robots can travel from cell to cell in any of the four directions, north, south, east or west as long as there isn’t a wall in the way. The robots Tyko imagines are highly advanced so it is not an issue if the paths of two robots overlap, one will simply jump over the other (or use some other extravagant mechanism, Tyko has not decided on the details yet).
This actually turns out to be a pretty fun algorithmic problem, maybe even worth considering for the upcoming contest. However, since Tyko is so busy preparing problems he doesn’t have time to implement this robot system himself so now he asks you to do it for him.
Input
The first line of input contains three integers $R$, $C$ and $N$ ($1 \leq R, C \leq 400$ and $1 \leq N \leq 200$), the number of rows and columns of the grid on which the robots will travel, and the number of deliveries, respectively.
The following $R$ lines describe the map. Each of these lines contain $C$ characters, each of which is either “#” (for squares that cannot be traversed by a robot), “.” for empty squares, “R” for squares initially containing a robot or “P” for squares containing a person who has requested a delivery.
It is guaranteed that there are exactly $N$ squares containing “R”, and exactly $N$ squares containing “P”. It is also guaranteed that there exists a matching of robots to people so that each robot can reach the person it is matched to.
Output
A single integer. The minimum amount of time needed to make all deliveries, if all robots start simultaneously and each robot delivers to at most one person.
Scoring
|
Group |
Points |
Constraints |
|
$1$ |
$13$ |
There are no squares with “#” and $N = 1$ |
|
$2$ |
$10$ |
There are no squares with “#” and $N \leq 3$ |
|
$3$ |
$19$ |
$N = 1$ |
|
$4$ |
$14$ |
$N \leq 10$ |
|
$4$ |
$17$ |
$N \leq 20$ |
|
$5$ |
$27$ |
$N \leq 200$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 6 3 .R...# ####P# P..##R P..R.. |
6 |
