Indian Computing Olympiad

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

---