103001: [Atcoder]ABC300 B - Same Map in the RPG World
Description
Score : $200$ points
Problem Statement
Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.
We have grids $A$ and $B$ with $H$ horizontal rows and $W$ vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the $i$-th row from the top and $j$-th column from the left in $A$ and $B$ are denoted by $A_{i, j}$ and $B_{i, j}$, respectively.
The following two operations are called a vertical shift and horizontal shift.
- For each $j=1, 2, \dots, W$, simultaneously do the following:
- simultaneously replace $A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j}$ with $A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}$.
- For each $i = 1, 2, \dots, H$, simultaneously do the following:
- simultaneously replace $A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W}$ with $A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}$.
Is there a pair of non-negative integers $(s, t)$ that satisfies the following condition? Print Yes if there is, and No otherwise.
- After applying a vertical shift $s$ times and a horizontal shift $t$ times, $A$ is equal to $B$.
Here, $A$ is said to be equal to $B$ if and only if $A_{i, j} = B_{i, j}$ for all integer pairs $(i, j)$ such that $1 \leq i \leq H$ and $1 \leq j \leq W$.
Constraints
- $2 \leq H, W \leq 30$
- $A_{i,j}$ is
#or., and so is $B_{i,j}$. - $H$ and $W$ are integers.
Input
The input is given from Standard Input in the following format:
$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}$
Output
Print Yes if there is a conforming integer pair $(s, t)$; print No otherwise.
Sample Input 1
4 3 ..# ... .#. ... #.. ... .#. ...
Sample Output 1
Yes
By choosing $(s, t) = (2, 1)$, the resulting $A$ is equal to $B$.
We describe the procedure when $(s, t) = (2, 1)$ is chosen. Initially, $A$ is as follows.
..# ... .#. ...
We first apply a vertical shift to make $A$ as follows.
... .#. ... ..#
Then we apply another vertical shift to make $A$ as follows.
.#. ... ..# ...
Finally, we apply a horizontal shift to make $A$ as follows, which equals $B$.
#.. ... .#. ...
Sample Input 2
3 2 ## ## #. .. #. #.
Sample Output 2
No
No choice of $(s, t)$ makes $A$ equal $B$.
Sample Input 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
Sample Output 3
Yes
Sample Input 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
Sample Output 4
Yes
Input
题意翻译
给定两个大小为 $H \times W$ 的矩阵 $A$ 和 $B$，问能否通过把矩阵 $A$ 循环右移 $s$ 次和循环下移 $t$ 次，使得 $A$ 和 $B$ 的每个元素都一样。 - 下移规则：对于 $ 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} $。Output
问题描述
Takahashi 正在开发一款 RPG。他决定编写一个代码来检查两个地图是否相等。
我们有两个网格 $A$ 和 $B$，分别有 $H$ 行和 $W$ 列。每个网格的单元格上都写有一个符号 # 或 .。
在 $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)$，满足以下条件？如果有，则输出 Yes，否则输出 No。
- 执行 $s$ 次垂直平移和 $t$ 次水平平移后，$A$ 等于 $B$。
这里，$A$ 和 $B$ 相等，当且仅当对于所有整数对 $(i, j)$，使得 $1 \leq i \leq H$ 和 $1 \leq j \leq W$ 时，$A_{i, j} = B_{i, j}$。
约束条件
- $2 \leq H, W \leq 30$
- $A_{i,j}$ 是
#或.，$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}$
输出
如果存在满足条件的整数对 $(s, t)$，则输出 Yes；否则输出 No。
样例输入 1
4 3 ..# ... .#. ... #.. ... .#. ...
样例输出 1
Yes
选择 $(s, t) = (2, 1)$，使得得到的 $A$ 等于 $B$。
当 $(s, t) = (2, 1)$ 时，我们将按照以下步骤进行：
..# ... .#. ...
首先执行垂直平移，使得 $A$ 如下所示：
... .#. ... ..#
然后再次执行垂直平移，使得 $A$ 如下所示：
.#. ... ..# ...
最后执行水平平移，使得 $A$ 如下所示，等于 $B$：
#.. ... .#. ...
样例输入 2
3 2 ## ## #. .. #. #.
样例输出 2
No
不存在使得 $A$ 等于 $B$ 的 $(s, t)$ 选择。
样例输入 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
样例输出 3
Yes
样例输入 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
样例输出 4
Yes