Showcase#5160
The supermarket hall is a rectangular area with dimensions m \times n, filled with showcases each measuring 1 \times 1. These showcases are aligned parallel to the supermarket walls, and their distances from the walls are whole numbers.
A new super showcase, measuring k \times 1, has been delivered and placed in one corner of the supermarket. Your task is to move it to the opposite corner without rotating it, only sliding it parallel to the walls. Write a program to determine the minimum number of showcases that need to be removed to achieve this.
The first line of input contains three natural numbers , , and (M, N \leq 100, K \leq M). The initial and final positions of the super showcase are as depicted in the top image. The next line contains a non-negative integer , representing the number of showcases (0 \leq V \leq N \cdot M). The following lines each contain a pair of non-negative integers indicating the position of a showcase. The first integer (from to M-1) is the distance from the left wall, and the second (from to N-1) is the distance from the bottom wall. It is guaranteed that no showcases are present where the super showcase initially rests.
On the first line of the output, print the minimum number of showcases that need to be removed. On the second line, provide a possible path for moving the super showcase, using a string of uppercase Latin letters representing the following moves:
U – move unit up,
D – move unit down,
L – move unit left,
R – move unit right.
The length of the string should not exceed N \times M. If multiple routes are possible, you may print any one of them.
Example 1