Editorial for COI '09 #4 Roboti
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us first solve a simple problem: what if there was only one robot, and the answer to the move function was
- Locating the precise location of the robot
- Moving it to the selected extraction point
We can determine the absolute location of the robot using DFS. We create a relative map of the warehouse starting in
What happens if there is another robot, and the function returns their distance? First, note that the function can still be interpreted in success/fail terms. If the distance changes, the robot moved, if not, it didn't. However, the second problem is that the robot can, and most will, hit the other robot. This can be identified.
First of all, the robots can only hit each other if their distance is
At this point, there are a number of ways you may proceed. Since now we have the relative location of both robots, we can simply continue to explore the map with the first robot until we can safely overlay the maps and then move both robots to the extraction point. Another good way is to note that if the robots hit each other not moving can be treated as exchanging places and numbers.
Comments