Same Map in the RPG World

题目描述

Takahashi 正在开发一款 RPG。他决定编写一个代码来检查两个地图是否相同。

我们有大小为 $H$ 行 $W$ 列的网格 $A$ 和 $B$。网格中的每个格子上都写有符号 # 或 $.$。
记从上数第 $i$ 行、从左数第 $j$ 列的格子在 $A$ 和 $B$ 上写的符号分别为 $A_{i, j}$ 和 $B_{i, j}$。 下面两种操作称为竖直移动和水平移动。

对于每个 $j=1, 2, \dots, W$，同时执行下列操作： 同时用 $A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}$ 替换 $A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j}$。

对于每个 $i = 1, 2, \dots, H$，同时执行下列操作： 同时用 $A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}$ 替换 $A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W}$。

是否存在一对非负整数 $(s, t)$ 满足下述条件？如果存在则输出 $Yes$，否则输出 $No$。

对 $A$ 先进行 $s$ 次竖直移动再进行 $t$ 次水平移动后，$A$ 与 $B$ 相同。

这里，当且仅当对所有满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$ 都有 $A_{i, j} = B_{i, j}$ 时，才称 $A$ 与 $B$ 相同。

输入格式

输入从标准输入按以下格式给出： $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$。

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

Yes

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

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

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

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

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

No

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

Yes

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

Yes

提示

$2 \leq H, W \leq 30$ $A_{i,j}$ 是 # 或 $.$，$B_{i,j}$ 亦然。 $H$ 和 $W$ 为整数。通过选择 $(s, t) = (2, 1)$，得到的 $A$ 等于 $B$。
我们描述在选择 $(s, t) = (2, 1)$ 时的过程。最初，$A$ 如下。

我们首先做一次竖直移动使 $A$ 如下。

然后我们再做一次竖直移动使 $A$ 如下。

最后我们做一次水平移动使 $A$ 如下，该结果与 $B$ 相等。
没有任何 $(s, t)$ 的选择能使 $A$ 等于 $B$。

标签: AtCoder|abc300B

来源

AtCoder|abc300B