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,N}$ $T_{1,1}T_{1,2}\ldots T_{1,N}$ $\vdots$ $T_{N,1}T_{N,N}$

输出格式

如果可以通过 $90$ 度的旋转和位移将 $S$ 精确匹配为 $T$，则输出 $Yes$，否则输出 $No$。

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

Yes

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

No

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

Yes

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

No

提示

$1 \leq N \leq 200$ $S$ 和 $T$ 由 # 和 $.$ 组成。 $S$ 和 $T$ 中每个至少包含一个 #。我们可以通过将 $S$ 逆时针旋转 $90$ 度并平移来匹配 $T$。
不可能通过 $90$ 度的旋转和位移来匹配它们。
$S$ 与 $T$ 中的图形可能不是连通的。
请注意不允许只对图形的一部分进行旋转或平移；只能对整个图形进行旋转或平移。

标签: AtCoder|abc218C

来源

AtCoder|abc218C