D. Parquet Re-laying

Codeforces

IDCF778D

Time2000ms

Memory512MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

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. <center>![image](https://espresso.codeforces.com/6388306d189bd8b77c20159f436fbe1284ea21e7.png)</center>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 100 000 commands. ## Input 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. ## Output 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. [samples] ## Note In the first sample test first operation is to rotate two rightmost tiles, after this all tiles lie vertically. Second operation is to rotate two leftmost tiles, after this we will get desired configuration. <center>![image](https://espresso.codeforces.com/2678a2f0d5d4969a1e6324bd816944d6ce2edc60.png)</center>

Peter 决定在一间大小为 $n × m$ 的房间中铺设拼花地板，拼花由大小为 $1 × 2$ 的瓷砖组成。当工人铺设完地板后，发现瓷砖的图案不符合 Peter 的喜好，因此需要重新铺设。工人认为完全拆除地板再重新铺设非常困难，于是决定每小时执行一次操作：移除两个组成 $2 × 2$ 正方形的瓷砖，将它们旋转 90 度后放回原位。他们不知道如何使用这些操作得到目标配置，甚至不确定是否可能实现。请帮助 Peter 为工人制定一个计划，或告知这是不可能的。计划中的操作次数不得超过 $100 000$ 次。第一行包含整数 $n$ 和 $m$，表示房间的尺寸（$1 ≤ n, m ≤ 50$），其中至少有一个是偶数。接下来 $n$ 行，每行包含 $m$ 个字符，描述当前拼花瓷砖的配置。每个字符代表半块瓷砖的位置，字符 '_L_'、'_R_'、'_U_' 和 '_D_' 分别对应左、右、上、下半部分。再接下来 $n$ 行，每行包含 $m$ 个字符，以相同格式描述目标配置。第一行输出整数 $k$，表示操作次数。接下来 $k$ 行，每行描述一次操作，操作由执行操作的左上角半块瓷砖的坐标（行和列）指定。如果无解，请在第一行输出 _-1_。在第一个样例中，第一次操作是旋转最右边的两个瓷砖，之后所有瓷砖都变为竖直排列；第二次操作是旋转最左边的两个瓷砖，之后得到目标配置。 ## Input 第一行包含整数 $n$ 和 $m$，表示房间的尺寸（$1 ≤ n, m ≤ 50$），其中至少有一个是偶数。接下来 $n$ 行，每行包含 $m$ 个字符，描述当前拼花瓷砖的配置。每个字符代表半块瓷砖的位置，字符 '_L_'、'_R_'、'_U_' 和 '_D_' 分别对应左、右、上、下半部分。再接下来 $n$ 行，每行包含 $m$ 个字符，以相同格式描述目标配置。 ## Output 第一行输出整数 $k$，表示操作次数。接下来 $k$ 行，每行描述一次操作，操作由执行操作的左上角半块瓷砖的坐标（行和列）指定。如果无解，请在第一行输出 _-1_。 [samples] ## Note 在第一个样例中，第一次操作是旋转最右边的两个瓷砖，之后所有瓷砖都变为竖直排列；第二次操作是旋转最左边的两个瓷砖，之后得到目标配置。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ \max(n,m) \leq 50 $ and $ n \cdot m $ even. Let $ C_{\text{init}}, C_{\text{target}} \in \{L, R, U, D\}^{n \times m} $ be the initial and target configurations, where each cell represents a half-tile. A tile is a pair of adjacent (horizontally or vertically) half-tiles forming a $1 \times 2$ or $2 \times 1$ domino. An **operation** consists of selecting a $2 \times 2$ square of cells centered at $(i,j)$ (top-left corner), such that the four half-tiles form two complete dominoes, and rotating the entire $2 \times 2$ block by 90 degrees clockwise. **Constraints** 1. $ 1 \leq n, m \leq 50 $ 2. At least one of $ n, m $ is even 3. Each configuration $ C_{\text{init}}, C_{\text{target}} $ is valid: every half-tile is paired with exactly one neighbor to form a domino. 4. The number of operations $ k \leq 100{,}000 $ **Objective** Find a sequence of operations (each specified by the top-left coordinate $ (i,j) $ of the $2 \times 2$ square) such that applying them in order transforms $ C_{\text{init}} $ into $ C_{\text{target}} $. If impossible, output $-1$.

Samples

Input #1

2 3
ULR
DLR
LRU
LRD

Output #1

2
1 2
1 1

Input #2

4 3
ULR
DLR
LRU
LRD
ULR
DUU
UDD
DLR

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Parquet Re-laying",
    "description": {
      "content": "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 Pete",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF778D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 Pete...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Peter 决定在一间大小为 $n × m$ 的房间中铺设拼花地板，拼花由大小为 $1 × 2$ 的瓷砖组成。当工人铺设完地板后，发现瓷砖的图案不符合 Peter 的喜好，因此需要重新铺设。\n\n工人认为完全拆除地板再重新铺设非常困难，于是决定每小时执行一次操作：移除两个组成 $2 × 2$ 正方形的瓷砖，将它们旋转 90 度后放回原位。\n\n他们不知道如何使用这些操作得到目标配置，甚至不确定是否可能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ \\max(n,m) \\leq 50 $ and $ n \\cdot m $ even.  \nLet $ C_{\\text{init}}, C_{\\text{target}} \\in \\{L, R, U, D\\}^{n \\times m} $ be the initial and targe...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments