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:
- the first line of the input file contains a positive integer N<=20, 
designating the side of the square maze.
- each of the subsequent N lines contain N numbers separated by a space 
character. Each number is a 0 or a 1. These lines are used to represent the 
maze.

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
Input
5
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0

Output
NOPATH

Example 2
Input
5
1 1 1 1 0
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 1 1 1 1

Output
4
DDDD
LLLL