First Hellenic Internet Programming Contest
30 November 1996


Problem 1 - Mazes and Monsters

Two monsters are placed in a NxN maze. The good monster is placed at the top left corner, whereas the evil one is placed at the bottom right corner of the maze. Each maze cell contains either a 1 or a 0. The monsters walk only up, down, left and right (NOT diagonally), in cells which contain a 1. The monsters are met, if they stand on the same cell. You must find the minimum number of steps each monster should perform in order to meet. Note, that at each turn, both monsters should perform a step (i.e. it is not allowed for a monster to stay at the same position, while the other has performed a step). Also, depending on the maze content, the two monsters may never meet.

Input
Your program should read the input data from the file INPUT1.TXT as follows:

Output
Your program should write the output into the file OUTPUT1.TXT as follows:

  • if it is impossible for the two monsters to meet, the first line of the file should contain the string ``NOPATH''.
  • if there is a ``meeting'' path, then the first line should contain the minimum number of steps that the monsters should perform in order to meet.
  • the next line contains a set of characters that indicates the path that the good monster should follow. These characters must be either U (for up), D (for down), L (for left) and R (for right). No space character should be placed between these characters.
  • the next line contains a set of characters that indicates the path that the evil monster should follow. Again, these characters must be U, D, L, or R, whereas no space should be placed between these characters.

    Example 1

    Example 2


    In order to get the ASCII files of the problem click here.