J1 习题-13 王国之心的营救任务

题目描述

在伟大航路上的冒险中，路飞终于在藏宝图的指引下来到了传说中的王国之心。为了营救被困的伙伴娜美，他必须解开古老的机关之谜。洞口的墙壁上有一个精密的凹陷图案，相传只有真正的龙之匙才能嵌入其中。

路飞已经在王城的宝箱中得到了一把神秘的钥匙，他需要你的帮助来判断这是否就是传说中的龙之匙。钥匙可以任意旋转 $(0°,90°,180°,270°)$ 和平移，但因为有正反面之分，因此不能翻转，但他可以多次尝试。对了，由于制作工艺的原因，要求钥匙完美嵌入，即没有钥匙之外多余空白的部分。

已知钥匙和凹陷处都分别用一张图表示，大小都是 $n \times n$ 。钥匙图中 # 表示钥匙的信息，. 表示空白部分；凹陷图中 # 表示平整的墙壁，. 表示凹陷的部分。

输入格式

本题有多组数据：

第一行一个整数 $t$，表示数据的组数；

每组数据 $n \times 2+1$ 行：

• 第一行一个整数 $n$，表示图案的尺寸；
• 接下来 $n$ 行，每行 $n$ 列，表示钥匙图上的符号分布；
• 接下来 $n$ 行，每行 $n$ 列，表示凹陷图上的符号分布。

输出格式

每组测试用例输出一行一个单词，如果钥匙能嵌入凹陷处，则输出 Yes，否则输出 No。

样例输入

2
5
.....
.....
...#.
..###
....#
#####
#.###
#..##
..###
#####
5
.....
.....
...#.
..###
....#
#####
#####
#..##
...##
#####

样例输出

Yes
No

样例分析

第一组样例：把钥匙顺时针旋转 $90°$，然后左移两格，再往上一格，就可以嵌入凹陷处了。

数据范围

对于 $100\%$ 的数据： $1 \le t \le 5$，$1 \le n \le 500$。