AT_abc300_b [ABC300B] Same Map in the RPG World

题目描述

高桥君正在制作 RPG。他决定编写一个程序，用于判断两张 RPG 世界地图是否一致。

有两个大小为 $H$ 行 $W$ 列的网格 $A$ 和 $B$。每个网格的每个格子上都写有 # 或 .。
$A$ 和 $B$ 的第 $i$ 行第 $j$ 列的字符分别记作 $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)$：

• 先对 $A$ 进行 $s$ 次纵向平移，再进行 $t$ 次横向平移后，$A$ 与 $B$ 完全一致。

这里，$A$ 与 $B$ 完全一致，指的是对于所有满足 $1 \leq i \leq H, 1 \leq j \leq W$ 的整数对 $(i, j)$，都有 $A_{i,j} = B_{i,j}$。

如果存在这样的整数对 $(s, t)$，输出 Yes，否则输出 No。

输入格式

输入通过标准输入给出，格式如下：

$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}$

输出格式

如果存在满足条件的整数对 $(s, t)$，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

Yes

输入输出样例 #4

输入 #4

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

输出 #4

Yes

说明/提示

限制条件

• $2 \leq H, W \leq 30$
• $A_{i,j}, B_{i,j}$ 仅为 # 或 .
• $H, W$ 均为整数

样例解释 1

当 $(s, t) = (2, 1)$ 时，可以使 $A$ 和 $B$ 一致。下面说明 $(s, t) = (2, 1)$ 时的操作过程。初始时，$A$ 如下：

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

首先进行一次纵向平移，$A$ 变为：

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

再进行一次纵向平移，$A$ 变为：

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

最后进行一次横向平移，$A$ 变为，与 $B$ 完全一致：

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

样例解释 2

无论如何选择 $(s, t)$，都无法使 $A$ 和 $B$ 一致。

由 ChatGPT 4.1 翻译