配点 : 400 点
問題文
N 行 M 栏 2 网格
给出 A,B 。网格中的每个方块都被漆成白色或黑色。 # 是黑色的, . 表示它被漆成白色。
这里,将网格的相邻顶点更改为上、下、左、右。 4 对于每个网格,考虑由黑色绘制的单元形成的连接组件形状(位置无关紧要)的多重集。
另外,考虑旋转和反转某个连接组件的操作。
首先,旋转操作涉及旋转整个连接组件,如下图所示。 90 表示顺时针旋转。
###. ##.# ..## #..# #.#. -> #### ###. ..#.
反转操作是指将整个连通分量在列或行方向上平行反转,如下图所示。 通过旋转或翻转
###. .### ..## ##.. #.#. -> .#.# ###. .### ###. ###. ..## #.#. #.#. -> ..## ###. ###.
A 中集合中的每个元素任意次数, 判断是否与 B 中的匹配。 长度由
制約
- 1 \leq N, M \leq 1000
- A_i, B_i 是
您也可以写
.和 按字典顺序比较#组成的长度 要变为 M 字符串 (1 \leq i \leq N) - N, M 是一个整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \vdots A_N B_1 B_2 \vdots B_N
出力
如果可以匹配 Yes ,如果不可能
输出 No 。
入力例 1
4 4 .##. ..#. #... #..# .##. ...# ..#. .##.
出力例 1
Yes
网格 A 和
按字典顺序比较 B 有以下内容
由 # 代表
有 3 连接的组件。 (下图是平行排列,没有旋转。)
在
................ ..##....#....#.. ...#....#....... ................ ................ ...#....##...#.. ..##............ ................
A 的连接组件中,
- 左边的有旋转操作。 执行 2 次后,执行反转操作。 1 次如下图 匹配 B 的连接组件。
- 旋转中间的一个 匹配需要 1 次。
- 右边的匹配没有任何操作。
因此,可以匹配连接组件集,因此 Yes 请输出
入力例 2
5 6 ###... .#...# .....# ##..## .##... ..###. ....## ....## ##...# .##...
出力例 2
No
A 中连接的组件如下图所示。 2 其一,通过如下连接。 看来您可以匹配 B 的连接组件。然而,通过连接多个连接组件, 1 不能被视为两个连接的组件。
........ ........ .###.... ...###.. .###..#. ..#.###. ...#..#. .....##. ..#...#. -> .##...#. -> .....##. -> .....##. .....##. ..#..... ......#. ......#. ........ ........ ........ ........
入力例 3
5 15 ###.###.###.### ..#.#.#...#.#.. ###.#.#.###.### #...#.#.#.....# ###.###.###.### ###.###.###.### ..#.#.#...#...# ###.#.#.###.### #...#.#.#...#.. ###.###.###.###
出力例 3
Yes