比赛场次 578
比赛名称 4043级2023省选模拟赛8
比赛状态 已结束比赛成绩
开始时间 2023-03-29 18:40:00
结束时间 2023-03-29 22:00:00
开放分组 全部用户
注释介绍 van two
题目名称 Stamp Grid
输入输出 yinzhang.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 14 简单对比
用户 结果 时间 内存 得分
Gravatarzxhhh AAAAAAAAAAAAAA 0.006 s 2.46 MiB 100
Gravatarムラサメ AAAAAAAAAAAAAA 0.014 s 1.26 MiB 100
Gravatarender RRRRRRRRRRRRRR 0.000 s 0.00 MiB 0

Stamp Grid

★   输入文件:yinzhang.in   输出文件:yinzhang.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

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


画布可以看作一个 $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$