Stamp Grid

题目描述

一幅“印章画”是在一个 $N \times N$ 的画布上的黑白画，其中某些格子被涂黑，其他格子为空白。它可以用一个 $N\times N$ 的字符数组来描述（$1\le N\le 20$）。数组中第 $j$ 列的第 $i$ 个字符，如果画布对应格子有墨水则为 *，否则为 .。

Bessie 有一幅她想要制作的印章画，因此 Farmer John 借给她一个 $K\times K$ 的印章（$1\le K\le N$）以及一张空的 $N \times N$ 画布。Bessie 可以重复执行：将印章顺时针旋转 $90^{\circ}$，并把印章盖在网格上的任意位置，只要印章完全位于网格内部。

形式化地，一次盖章时，Bessie 选择整数 $i,j$，满足 $i \in [1,N-K+1]$ 且 $j \in [1, N-K+1]$；对于所有满足 $1 \le i', j' \le K$ 的 $(i',j')$，若印章在 $(i', j')$ 处有墨水，则画布格子 $(i+i'-1, j+j'-1)$ 被涂黑。Bessie 可以在任意两次盖章之间旋转印章。画布上的格子一旦被涂黑，就会一直保持为黑色。

Farmer John 想知道 Bessie 是否可能用他的印章制作出她想要的印章画。对于 $T$（$1 \le T \le 100$）组测试数据，请帮助 Farmer John 回答这个问题。

输入格式

第一行输入包含 $T$，表示测试用例数量。

每个测试用例以一个整数 $N$ 开始，接下来有 $N$ 行，每行包含一个由 * 和 . 组成的字符串，表示 Bessie 想要的印章画。下一行包含 $K$，并接着有 $K$ 行，每行包含一个由 * 和 . 组成的字符串，表示 Farmer John 的印章。

相邻测试用例之间用空行分隔。

输出格式

对于每个测试用例，分别输出一行 "YES" 或 "NO"。

4

2
**
*.
1
*

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

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

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

YES
YES
NO
YES

提示

在第一组测试用例中，Bessie 可以执行如下盖章序列： 在 $(1,1)$ 盖章 在 $(1,2)$ 盖章 在 $(2,1)$ 盖章

在第二组测试用例中，Bessie 可以执行如下盖章序列： 在 $(2,2)$ 盖章 在 $(2,1)$ 盖章 旋转 $90^{\circ}$ 旋转 $90^{\circ}$ 在 $(1,2)$ 盖章

在第三组测试用例中，不可能涂黑中间的格子。

在第四组测试用例中，Bessie 可以执行如下盖章序列： 旋转 $90^{\circ}$ 在 $(1,1)$ 盖章 在 $(1,2)$ 盖章 在 $(2,2)$ 盖章

题目致谢：Benjamin Qi 和 Claire Zhang

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze