We have a rectangle maze with dimensions nxm (where n<=20, m<=20). The top left and
the bottom right positions of the maze are marked by 0, and all other maze positions by
one of the numbers 1, 2, 3, 4. The aim of the game is to enter the maze at the top left
corner and leave it from the bottom right corner by following the shortest path moving
only to the right, left, down and up. The constraint that we have to obey in order to
follow a path from the entrance to the exit is to move from a 1, to a 2, to a 3, to a 4,
to a 1 and so on, in a cyclic way. From the start position you can only move to a 1
position. You can move to the exit position either from the neighboring upper or
neighboring left cell of the exit position.
 |
Input: INPUT DATA (file INPUT.TXT) The first line contains the integers n and m. Each of the next n lines contains m integers representing the maze. |
|
Output: OUTPUT DATA (file OUTPUT.TXT) This file will consist of two lines, containing the number of steps and a string of characters respectively. The string consists of the characters D (for down), U (for up), L (for left) and R (for right), the steps along the shortest path to the exit. |
|
Example Input 5 4 0 1 2 3 3 2 1 4 4 1 2 1 1 4 3 2 2 3 4 0 Output 7 RRRDDDD |
|
Remark: you may assume that there is always a solution to the problem. |
Time-limit for each test: 5 seconds.
Maximal score: 30 points