Score : $300$ points

问题描述

在二维网格（由正方形格子组成）上有两个图形 $S$ 和 $T$。

$S$ 在一个具有 $N$ 行和 $N$ 列的网格内，由其中 $S_{i,j}$ 为 # 的格子构成。
$T$ 同样位于该具有 $N$ 行和 $N$ 列的网格内，并由其中 $T_{i,j}$ 为 # 的格子构成。

判断是否可以通过 $90$-度旋转和平移精确匹配 $S$ 和 $T$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have two figures $S$ and $T$ on a two-dimensional grid with square cells.

$S$ lies within a grid with $N$ rows and $N$ columns, and consists of the cells where $S_{i,j}$ is #.
$T$ lies within the same grid with $N$ rows and $N$ columns, and consists of the cells where $T_{i,j}$ is #.

Determine whether it is possible to exactly match $S$ and $T$ by $90$-degree rotations and translations.

Constraints

• $1 \leq N \leq 200$
• Each of $S$ and $T$ consists of # and ..
• Each of $S$ and $T$ contains at least one #.

Input

Input is given from Standard Input in the following format:

$N$

$S_{1,1}S_{1,2}\ldots S_{1,N}$

$\vdots$

$S_{N,1}S_{N,2}\ldots S_{N,N}$

$T_{1,1}T_{1,2}\ldots T_{1,N}$

$\vdots$

$T_{N,1}T_{N,2}\ldots T_{N,N}$

Output

Print Yes if it is possible to exactly match $S$ and $T$ by $90$-degree rotations and translations, and No otherwise.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match $S$ to $T$ by rotating it $90$-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by $90$-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of $S$ and $T$ may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

update @ 2024/3/10 09:38:41