← 返回题目列表

AtCoder · pakencamp_2025_day1_h

H. 典型的问题

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

配点 : 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