Rescue the hamsters#213
One day, a group of hamsters appeared at a scientist's door, sniffling quietly and wiping their tearful eyes. "What happened?" the scientist asked, and they delivered a troubling message: two hamsters had gotten lost in the ventilation system designed to cool a supercomputer. The scientist decided to help the hamsters rescue their friends. The problem is that the only way to assist them is by sending commands via radio. Help the scientist write a program to save the hamsters.
The ventilation maze is a flat rectangular plate with cut-out sections. There is exactly one exit in the maze. The hamsters are not clever or resourceful, and cannot escape on their own. However, they can follow a set of commands. Commands are given to both hamsters simultaneously, and they move at the same speed. The commands are as follows:
Move right — R
Move left — L
Move up — U
Move down — D
For simplicity, assume the maze consists of cells. Each cell can be a passage, a wall, or an exit. The hamsters can occupy the same cell at the same time. They cannot pass through ventilation walls. Moreover, they are so disoriented from wandering that they can leave the maze only together. If only one hamster reaches the exit cell, it does not leave the maze and continues executing commands.
The first line contains two integers and , the vertical and horizontal dimensions of the maze, respectively. The next lines contain characters each, where each character can be: * — exit, — first hamster in a passage cell, — second hamster in a passage cell, — free cell, # — wall. H, W \leq 100.
On the first line, output the length of the program. On the second line, output the program for the hamsters. If there is no solution, output -1.
Example 1