3870. [USACO23 Feb Bronze] Stamp Grid

【题目描述】

我们要用一个印章在一个画布上做一幅画。

画布可以看作一个 $N×N$ 的网格矩阵，行列编号均为 $1 \sim N$。

初始时，画布网格中所有的单元格都是白色的，单元格 $(i,j)$ 指其中第 $i$ 行第 $j$ 列的单元格，我们希望将其中一部分单元格涂黑。

印章可以看作一个 $K×K$ 的网格矩阵，行列编号均为 $1 \sim K$，单元格 $(i,j)$ 指其中第 $i$ 行第 $j$ 列的单元格，其中一部分单元格中包含墨水。

使用印章在画布上作画时，按如下操作：

$（1）$、在每次盖下印章前可以调整印章的角度，将印章顺时针旋转 $0,90,270,360$ 度，即印章网格可能旋转。

$（2）$、可以在画布网格的任意位置按下印章，但前提是印章覆盖区域必须完全在画布网格内。具体来说，每次盖下印章即为：选择一对整数 $(i,j)$，要求 $i∈[1,N−K+1]$ 且 $j∈[1,N−K+1]$，对于每个 $(i′,j′)（1≤i′,j′≤K）$，如果当前印章网格的单元格 $(i′,j′)$ 中包含墨水，则画布网格的单元格 $(i+i′−1,j+j′−1)$ 被涂黑。多次盖章覆盖区域可以重叠,一旦某单元格被涂黑，那么它将保持黑色。

给定目标画作以及印章网格，请你判断能否完成画作。

【输入格式】

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含一个空行。

下一行包含一个整数 $N$。

接下来 $N$ 行，包含一个 $N×N$ 的字符矩阵，表示目标画作，其中第 $i$ 行第 $j$ 个字符表示单元格 $(i,j)$ 的目标颜色，每个字符要么是 $*$（表示黑色），要么是 $.$（表示白色）。

下一行包含一个整数 $K$。

接下来 $K$ 行，包含一个 $K×K$ 的字符矩阵，表示印章网格，其中第 $i$ 行第 $j$ 个字符表示单元格 $(i,j)$ 的墨水情况，每个字符要么是 $*$（表示包含墨水），要么是 $.$（表示不含墨水）。

【输出格式】

每组数据输出一行结果，能够完成画作输出 YES，否则输出 NO。

【样例输入】

4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.

【样例输出】

YES
YES
NO
YES

【样例解释】

第一组数据，贝茜可以如下盖章：

 以画布网格中单元格 $(1,1)$ 作为左上角，盖下印章。

 以画布网格中单元格 $(1,2)$ 作为左上角，盖下印章。

 以画布网格中单元格 $(2,1)$ 作为左上角，盖下印章。

第二组数据，贝茜可以如下盖章：

 以画布网格中单元格 $(2,2)$ 作为左上角，盖下印章。

 以画布网格中单元格 $(2,1)$ 作为左上角，盖下印章。

 顺时针旋转印章 $180$ 度。

 以画布网格中单元格 $(1,2)$ 作为左上角，盖下印章。

第三组数据，无法完成画作。

第四组数据，贝茜可以如下盖章：

 顺时针旋转印章 $90$ 度。

 以画布网格中单元格 $(1,1)$ 作为左上角，盖下印章。

 以画布网格中单元格 $(1,2)$ 作为左上角，盖下印章。

 以画布网格中单元格 $(2,2)$ 作为左上角，盖下印章。

【数据规模与约定】

$1≤T≤100,1≤N≤20,1≤K≤N$