407381: GYM102780 E Printed circuit board

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Printed circuit boardtime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output

Printed circuit boards are one of the key notions of modern electronics. There are a huge number of programs for working with the printed circuit boards, and for transferring the complete drawing to the surface of the board, there exist quite a lot of methods (sometimes very exotic). One way to transfer a picture is to use a plotter, a device that can draw continuous lines on the surface. Write a program that, according to the printed circuit board drawing, will make up a set of commands for the plotter to draw this drawing.

The plotter works on a square grid of $$$n \times m$$$ size. The grid squares are numbered from left to right (first coordinate), and from top to bottom (second coordinate). The command for drawing a line consists of two numbers — the coordinates of the beginning of the line, and a sequence of letters "L", "R", "U", "D", which draw a line one cell from the current position to the left, right, up or down, respectively. For example, the "3 4 DRUL" command will draw a square with side 1 and the upper left corner at coordinates 3 4.

In order to minimize the time spent on drawing, the program should build a set of the minimum possible number of commands (continuous lines). If there are several such sets, then any of them is to be considered a solution.

Please note that:

  • Any cell of the board either does not contain a line, or contains one line, or two intersecting lines (intersection point);
  • A line can begin and end at the same point;
  • If two lines start at one point, then they can be combined into one line;
  • The line length cannot be less than 2 (the line cannot connect 2 adjacent squares);
  • A line or lines cannot begin or end in neighboring cells (the cells are considered neighboring if they have a common side);
  • A line cannot be drawn over an existing one.
Input

The first line of input contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 100$$$) — the size of the printed circuit board. This is followed by $$$n$$$ lines of $$$m$$$ characters in each. The following characters are used to encode a board picture:

  • "." ("Point", code 0x2E) — empty (blank) square;
  • "*" ("Asterisk", code 0x2A) — The beginning or end of the line, or the point where more than two lines meet;
  • "-" ("Minus", code 0x2D) - Horizontal line;
  • "|" ("Vertical bar", code 0x7C) — Vertical line;
  • "L" ("Capital L", code 0x4C) — The line connecting the upper and the right cells;
  • "J" ("Capital J", code 0x4A) — A line connecting the upper and the left cells;
  • "r" ("Lowercase r", code 0x72) — The line connecting the lower and the right cells;
  • "7" ("Digit 7", code 0x37) — The line connecting the lower and the left cells.

For any line in the image, there is a starting and a final point. The line can begin and end at the same point, then such a point is indicated as "*". Through one square either one line passes, or, if several lines intersect in this square, then they are considered connected, and the square contains the "*" sign. The passing of lines through one square without a connection is not possible. The signs "*" cannot be found in the neighboring cells (cells having a common side).

Output

The first line of the output contains the number $$$k$$$ ($$$0 \leq k \leq 10000$$$) — the number of commands. This is followed by $$$k$$$ lines, each of which describes a separate command. The command begins with two integers $$$x$$$ and $$$y$$$, separated by a blank space, — the coordinates of the beginning of the line. Further, also through a blank space, comes a sequence of capital letters "L", "R", "U" or "D", describing the line to be drawn. Letters go in a row without spaces. The command ends with a line feed.

ExamplesInput
3 4
r--*
*...
L--*
Output
1
4 3 LLLUURRR
Input
3 4
r--*
L--7
*--J
Output
1
1 3 RRRULLLURRR
Input
3 3
r-*
|.|
L-J
Output
1
3 1 LLDDRRUU
Input
5 5
..*..
..|..
*-*-*
..|..
..*..
Output
2
3 5 UUUU
1 3 RRRR
Note

Please, note that the board drawing is described in a line by line fashion and the commands use the "column row" coordinates.

加入题单

上一题 下一题 算法标签: