Anti-Tetris

2000ms

1048576K

Description:

Let us consider the game "Sticky Tetris". In this game, there is a field of $$$n \times m$$$ squares. Tiles appear on the field and the player can move the tiles.

Each tile is a $$$4$$$-connected set of at most $$$7$$$ squares.

Each new tile appears in any position that fits inside the field, does not intersect any other tile, and the top cell of the tile is at the top row of the field. The player can move the tile left, right, and down, and at any moment the tile must still entirely fit inside the field and must not intersect other tiles. The player can stop the tile at any position at any time. After that, it cannot be moved. Since this is "Sticky Tetris," the tile will not fall once stopped.

You are given a final configuration of a "Sticky Tetris" game. You need to restore a sequence of steps that leads to that configuration if it exists.

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 50$$$) — the size of the playing field.

The next $$$n$$$ lines contain a string of $$$m$$$ characters each. Each character could be either a '.', or lowercase English letter. Connected components of the same letter correspond to a single tile. Each tile consists of at most $$$7$$$ squares.

Output:

If there is no solution, print $$$-1$$$.

Otherwise, print $$$k$$$ — the number of different tiles that are placed on the field.

On the next $$$k$$$ lines print the sequence of steps for each of the tiles in the order they are placed.

Each line consists of a number $$$x$$$ followed by a string with steps. $$$x$$$ ($$$1 \le x \le m$$$) is the starting column of the leftmost square in the top row of the tile. The string consists of characters 'L' (for left), 'R' (for right), and 'D' (for down), describing the path of that tile, ending with a single character 'S' (for stop). The final position of the tile determines which tile is being placed. The string with steps can have at most $$$n \cdot m + 1$$$ characters.

Sample Input:

3 2
aa
ab
aa

Sample Output:

2
2 DS
1 S

Sample Input:

5 6
....dd
.ccccd
.cbbdd
.aab.a
aabbaa

Sample Output:

5
2 DDDS
4 DDLS
6 DDDS
2 DS
5 S

Sample Input:

5 3
...
aab
abb
aab
.bb

Sample Output:

-1

Informação

Provedor Codeforces

Código CF1578A