Showcase
The supermarket hall is a rectangular area with dimensions m×n, filled with showcases each measuring 1×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×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.
Input
The first line of input contains three natural numbers M, N, and K (M, N ≤ 100, K ≤ 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 V, representing the number of showcases (0 ≤ V ≤ N·M). The following V lines each contain a pair of non-negative integers indicating the position of a showcase. The first integer (from 0 to M−1) is the distance from the left wall, and the second (from 0 to N−1) is the distance from the bottom wall. It is guaranteed that no showcases are present where the super showcase initially rests.
Output
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 1 unit up,
D – move 1 unit down,
L – move 1 unit left,
R – move 1 unit right.
The length of the string should not exceed NxM. If multiple routes are possible, you may print any one of them.