← 返回题目列表

AtCoder · abc300_b

D. RPG世界中的同一张地图

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

分数: 200 点

问题陈述

高桥正在开发一款角色扮演游戏。 他决定编写一个代码来检查两个映射是否相等。

我们有网格 A 和 B 与 H 水平行和 W 垂直列。 网格中的每个单元格都有一个符号 上面写着 # or . 。
写在单元格上的符号 i从顶部开始的第行和 j从左起第 A 和 B 表示为 A_{i, j} 和 B_{i, j}。

以下两个操作称为 垂直移位 和 水平移位.

  • 对于每个 j=1, 2, \dots, W,同时执行以下操作:
    • 同时替换 A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} 与 A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
  • 对于每个 i = 1, 2, \dots, H,同时执行以下操作:
    • 同时替换 A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} 与 A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

是否存在一对非负整数 (s, t) 满足以下条件? 打印 Yes 如果有,并且 No 否则。

  • 应用垂直移位后 s 次和水平移位 t 次, A 等于 B.

在这里, A 据说等于 B 当且仅当 A_{i, j} = B_{i, j} 对于所有整数对 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W.

约束

  • 2 \leq H, W \leq 30
  • A_{i,j} is # or .,也是如此 B_{i,j}.
  • H 和 W 是整数。

输入

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

H W
A_{1,1}A_{1,2}\dots A_{1,W}
A_{2,1}A_{2,2}\dots A_{2,W}
\vdots
A_{H,1}A_{H,2}\dots A_{H,W}
B_{1,1}B_{1,2}\dots B_{1,W}
B_{2,1}B_{2,2}\dots B_{2,W}
\vdots
B_{H,1}B_{H,2}\dots B_{H,W}

输出

打印 Yes 如果存在一致的整数对 (s, t);打印 No 否则。


样本输入 1

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

示例输出 1

Yes

通过选择 (s, t) = (2, 1),结果 A 等于 B.
我们描述了当 选择 (s, t) = (2, 1) 。 最初, A 如下。

..#
...
.#.
...

我们首先应用垂直移位以使 A 如下。

...
.#.
...
..#

然后我们应用另一个垂直移位来使 A 如下。

.#.
...
..#
...

最后,我们应用水平移位以使 A 如下,等于 B.

#..
...
.#.
...

示例输入 2

3 2
##
##
#.
..
#.
#.

示例输出 2

No

没有选择 (s, t) 使 A 等于 B.


示例输入 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

示例输出 3

Yes

示例输入 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

示例输出 4

Yes