/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋君は RPG を作っています。高橋君は 2 枚の RPG 世界のマップが一致しているかを判定するプログラムを書くことにしました。
縦 H マス横 W マスの 2 つのグリッド A, B があります。グリッドの各マスには # と . のいずれかの文字が書かれています。
A と B の上から i 行目、左から j 列目に書かれている文字をそれぞれ A_{i, j}, B_{i, j} と呼びます。
次の 2 種類の操作をそれぞれ 縦方向のシフト, 横方向のシフト と呼びます。
- 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 が一致するとは、1 \leq i \leq H, 1 \leq j \leq W を満たす整数の組 (i, j) すべてに対して 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 は次のようになります。
.#. ... ..# ...
最後に、横方向のシフトを行います。A は次のようになり、これは B と一致しています。
#.. ... .#. ...
入力例 2
3 2 ## ## #. .. #. #.
出力例 2
No
どのように (s, t) を選んでも A と B を一致させることはできません。
入力例 3
4 5 ##### .#... .##.. ..##. ...## #...# ##### ...#.
出力例 3
Yes
入力例 4
10 30 ..........##########.......... ..........####....###.....##.. .....##....##......##...#####. ....####...##..#####...##...## ...##..##..##......##..##....# #.##....##....##...##..##..... ..##....##.##..#####...##...## ..###..###..............##.##. .#..####..#..............###.. #..........##................. ................#..........##. ######....................#### ....###.....##............#### .....##...#####......##....##. .#####...##...##....####...##. .....##..##....#...##..##..##. ##...##..##.....#.##....##.... .#####...##...##..##....##.##. ..........##.##...###..###.... ...........###...#..####..#...
出力例 4
Yes
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