Anti-Tetris

题意翻译

考虑如下的一个“黏着方块”游戏。 - 游戏包含一块由 $n\times m$ 个方格组成的场地，砖块会出现在场地上，玩家可以移动这些砖块。 - 每块砖块都是一个由最多 $7$ 个方格组成的四联通块。 - 类似俄罗斯方块，每个砖块出现时，其第一行将位于场地的第一行（此处第一行为从上往下第一行，也就是说，初始时刻时该方块就已经完整的存在在盘面上），且其出现时不应当与其他任何砖块重合。玩家可以将砖块下移，左移或者右移，且在移动后依旧不能和任何其他砖块重合，且不能超出场地。玩家可以在任何合法的位置停止移动砖块，在这之后你将不再能移动这一砖块。当然，因为这是“黏着方块”，所以砖块并不会自然下落。在当前的方块被停止移动，下一个方块将不会出现。 给定一个游戏的终末状态，你需要还原这个游戏的玩家的各个操作。即，你需要给出盘面上每个方块的初始出现位置和玩家的操作序列，来达到终末状态。如若无解，输出 $-1$。 $1 \le n,m \le 50$。 输入共 $n+1$ 行。 - 第一行，两个整数 $n,m$，意义如题所示。 - 接下来的 $n$ 行，每行一个长度为 $m$ 的字符串。每个字符均为 $.$ （代表空白）或一个英文小写字母其中之一。相接的相同英文字母属于一个砖块，保证每个砖块的大小均不超过七个方格。 输出为一行或 $k+1$ 行。 - 若无解，输出一行一个整数 $-1$。 - 若有解，输出 $k+1$ 行。 - 第一行一个整数 $k$ ，代表盘面上的砖块总数。 - 接下来的 $k$ 行，每行一个整数 $x$ 和一个字符串。$x$ 为你所指定的某个砖块最左位置所处的行，字符串由‘L’,'R','D','S'四种字符组成，分别代表左移，右移，下移和终止。仅有最后一个字符应当为'S'。每个字符串最多由 $n\times m+1$个字符组成。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

3 2
aa
ab
aa

输出样例 #1

2
2 DS
1 S

输入样例 #2

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

输出样例 #2

5
2 DDDS
4 DDLS
6 DDDS
2 DS
5 S

输入样例 #3

5 3
...
aab
abb
aab
.bb

输出样例 #3

-1