AT_abc218_c [ABC218C] Shapes

题目描述

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

$S$ 位于 $N$ 行 $N$ 列的网格中，由所有 $S_{i,j}$ 为 # 的格子组成。
$T$ 也位于 $N$ 行 $N$ 列的网格中，由所有 $T_{i,j}$ 为 # 的格子组成。

请判断是否可以通过若干次 $90$ 度旋转和平移操作，使 $S$ 与 $T$ 完全重合。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

如果可以通过若干次 $90$ 度旋转和平移操作使 $S$ 与 $T$ 完全重合，输出 Yes，否则输出 No。

样例 1

输入

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

输出

Yes

样例 2

输入

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

输出

No

样例 3

输入

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

输出

Yes

样例 4

输入

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

输出

No

说明/提示

限制条件

• $1 \leq N \leq 200$
• $S,T$ 仅由 # 和 . 组成
• $S,T$ 至少各包含一个 #

样例解释 1

可以将 $S$ 逆时针旋转 $90$ 度并平移，使其与 $T$ 完全重合。

样例解释 2

无法通过若干次 $90$ 度旋转和平移操作使两者重合。

样例解释 3

$S$ 和 $T$ 不一定是连通的。

样例解释 4

请注意，旋转和平移操作是针对整个 $S,T$ 进行的，而不是针对每个连通分量分别操作。

由 ChatGPT 4.1 翻译