304052: CF778D. Parquet Re-laying
Memory Limit:512 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Parquet Re-laying
题意翻译
Peter决定在大小为n×m的房间里放一个拼花,拼花是由大小为1×2的瓷砖组成。当工人们铺设拼花地板时,很明显,瓷砖的图案看起来不像Peter喜欢的,工人们将不得不重新铺设它。 工人们决定把整块拼花地板搬开,然后重新铺设,这是一项非常困难的任务,所以他们决定每小时做一次这样的操作:把两块拼花地板拆下来,形成一个2×2的正方形,把它们旋转90度,再放回原来的位置。 帮助Peter为工人们制定一个计划,或者告诉他们这是不可能的。计划最多包含100000条命令。 输入格式 第一行包含整数n和m,房间大小(1<=n,m<=50)。至少有一个是偶数。 下面的n行分别包含m个字符,描述了当前拼花瓷砖的配置。每个字符表示半块的位置。字符“L”、“R”、“U”和“D”分别对应左、右、上、下半部分。 下面的n行包含m个字符,以相同的格式描述所需的配置。 输出格式 在第一行输出整数k,即操作数。在接下来的k行中,输出操作说明。操作是由执行操作的左上半块的坐标(行和列)指定的。 如果没有解,则在第一行输出-1。题目描述
Peter decided to lay a parquet in the room of size $ n×m $ , the parquet consists of tiles of size $ 1×2 $ . When the workers laid the parquet, it became clear that the tiles pattern looks not like Peter likes, and workers will have to re-lay it. The workers decided that removing entire parquet and then laying it again is very difficult task, so they decided to make such an operation every hour: remove two tiles, which form a $ 2×2 $ square, rotate them 90 degrees and put them back on the same place. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF778D/1811845168cb252f82588f73f367e9ae9a88d437.png)They have no idea how to obtain the desired configuration using these operations, and whether it is possible at all. Help Peter to make a plan for the workers or tell that it is impossible. The plan should contain at most $ 100000 $ commands.输入输出格式
输入格式
The first line contains integer $ n $ and $ m $ , size of the room ( $ 1<=n,m<=50 $ ). At least one of them is even number. The following $ n $ lines contain $ m $ characters each, the description of the current configuration of the parquet tiles. Each character represents the position of the half-tile. Characters 'L', 'R', 'U' and 'D' correspond to the left, right, upper and lower halves, respectively. The following $ n $ lines contain $ m $ characters each, describing the desired configuration in the same format.
输出格式
In the first line output integer $ k $ , the number of operations. In the next $ k $ lines output description of operations. The operation is specified by coordinates (row and column) of the left upper half-tile on which the operation is performed. If there is no solution, output -1 in the first line.
输入输出样例
输入样例 #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