Indian Computing Olympiad

Training Material


Basic Graph Algorithms→Amazing Robots (IOI 2003)

You are given two different mazes of size less than 20×20. Each maze contains a robots (R). Each maze also contains some guards G (at most 10). The mazes may not be the same and robots may not be in the same starting position.

         # # . # . # #         # # . # . # #
         R # . # G . .         . # . . . G .
         . . . . . # #         . . . . . # #
         . G . . . . .         . G . . . . .
         . . . # . . .         . . . . # R .
         # . # # # . .         # . # # # . .
      

Some cells on the maze are on the periphery, from where the robot can exit the maze. The aim is to get both robots to exit the maze without being captured by the guards.

To move the robot, you give an instruction of the form "move(direction)", where direction is one of North, South, East or West. If you say "move(N)", for instance, both robots move one step North, if they can. If either robot is blocked in this direction by a wall, the robot stays where it is. If either robot has left the maze already, the move applies only to the other robot.

The guards move either E-W or N-S on paths of fixed length. You are given the initial direction and the length of his path (this is between 2 and 4). Each time you move the robot, each guard moves one step along his path. If a guard has reached the end of his path, he turns around and moves back. You can assume that the paths followed by the guard are free of blocks, at no time do two guards stand on the same cell.

A guard catches a robot if

  • After some move, the guard and the robot are on the same cell
  • At some move, the guard and the robot cross each other by swapping cells.

Solution

Do a BFS on the state space.

Naive state space is

  1. Position of robots in each grid.
  2. Position of each guard.

This is too large (state space is 400 × 400 × ....).

Instead, compute the guards' positions as a function of time. In this case, we need to maintain:

  1. Position of robots in each grid.
  2. Current time T.

State space is still 400 × 400 × N, where N is the number of steps till they get out, which may become too large.

Observe that the guards' beats are of length 2, 3 or 4. Thus, each guard returns to his starting position after 2, 4 or 6 moves. Thus, we only need to keep track of time T modulo 2, 4 and 6. Since lcm(2,4,6) is 12, if we keep track of T modulo 12, we can recover all these three values.

In this problem, it is important to recognize that the path lengths for the guards allow you to cut down the state space of the BFS dramatically, to bring it within limits. Also, the number of edges is small because each node has at most 4 neighbours, corresponding to the N-S-E-W moves.