← 返回题目列表

Codeforces · 778/D

D. 镶木地板重新铺设

中文机器翻译题面 查看原题

Peter决定在n×m大小的房间里铺设镶木地板,该镶木地板由尺寸为1×2的瓷砖组成。当工人们铺设镶木地板时,很明显瓷砖图案看起来不像Peter喜欢的,工人们必须重新铺设。

工人们认为,拆除整个镶木地板然后重新铺设是一项非常困难的任务,因此他们决定每小时进行一次这样的操作:拆除两块瓷砖,形成一个 2 × 2 的正方形,将它们旋转 90 度,然后将它们放回原处。

他们不知道如何使用这些操作获得所需的配置,以及这是否可能。

帮助彼得为工人制定计划或告诉他这是不可能的。该计划最多应包含 100 000 个命令。

输入

第一行包含整数 n 和 m,房间的大小(1 ≤ n,m ≤ 50)。其中至少有一个是偶数。

以下 n 行每行包含 m 个字符,描述镶木地板砖的当前配置。每个字符代表半块的位置。字符“L”、“R”、“U”和“D”分别对应于左半部、右半部、上半部和下半部。

接下来的 n 行每行包含 m 个字符,以相同的格式描述所需的配置。

输出

在第一行输出整数k,即操作次数。接下来的k行输出操作的描述。该操作由执行操作的左上半块的坐标(行和列)指定。

如果无解,则在第一行输出-1。

示例

输入 #1

2 3
ULR
DLR
LRU
LRD

输出 #1

2
1 2
1 1

输入 #2

4 3
ULR
DLR
LRU
LRD
ULR
DUU
UDD
DLR

输出 #2

3
3 1
3 2
2 2

注意

在第一个示例测试中,第一个操作是旋转最右边的两个图块,之后所有图块都垂直放置。第二个操作是旋转最左边的两个图块,之后我们将得到所需的配置。