← 返回题目列表

AtCoder · past202303_j

J. 改变形状

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

问题陈述

给你数字 S 和 T 与 H 行和 W 列组成 # 和 ..
如图 S 给出为 H 字符串 S _ 1,S _ 2,\ldots,S _ H;的 j- 第一个字符 S _ i 表示位于 i第行和 j第列 S。图 T 类似地给出。

判断是否可以移动列 S 这样 S 将等于 T.

在这里,移动列 S 是以下操作。

  • 选择一个整数 s 之间 1 和 W,包括在内。
  • 然后,对于每个整数 i 这样 1 \leq i \leq H,同时执行以下操作:
    • 对于每个整数 j 这样 1 \leq j \leq W,同时替换 i第行和 j- 第列 i第行和 (j+s)第列 X.

这里,对于 x 这样 W \gt x, x第列表示 y- 第列,其中 y\ (1\leq y\leq W) 是唯一满足以下条件的整数 x-y 是的倍数 W.

约束

  • H 和 W 是整数。
  • 1 \le H,W
  • 1 \le H \times W \le 4 \times 10^5
  • S_i 和 T_i 是长度的字符串 W 组成 # 和 ..

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

输出

如果可以的话 S 等于 T,打印 Yes;否则,打印 No.


示例输入 1

3 4
##.#
##..
.#..
.###
..##
...#

示例输出 1

Yes

选择 s=2 将使 S 等于 T.


示例输入 2

3 4
##..
#..#
..##
..##
#..#
##..

示例输出 2

No

只能移动列,不能翻转图形。


示例输入 3

2 1
#
.
#
.

示例输出 3

Yes

情况可能是这样的 S=T.


示例输入 4

8 7
.#.....
..#....
....#..
#.....#
.#.....
..#....
....#..
#.....#
.....#.
......#
.#.....
...##..
.....#.
......#
.#.....
...##..

示例输出 4

Yes