Editorial for COI '09 #4 Roboti


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 1 if the robot moved and 0 if he didn't. The solution is a two-phase process:

  1. Locating the precise location of the robot
  2. 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 (0, 0) and visiting the fields in DFS order. Once the DFS is finished, we have a relative map of the warehouse with the robot in known coordinates. We now overlay this map with the map given in the input and obtain the absolute location of the robot. After this moving the robot to the extraction point is a straightforward task.

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 1. Now, if we have relative distance 1, and moving the robot fails, we can move the other robot in any direction (as long as the move is successful) and try the first robot again. If the robot moves this time, we know now that we have found the second robot.

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

There are no comments at the moment.