P7124: 图章网格

---

【题目描述】

【题目描述】
邮票画是在N×N上的黑白画画布，其中某些单元格是着墨的，而其他单元格是空白的。它可以用N×N个字符数组（1≤N≤20）来描述。如果画布在该正方形和处包含墨水，则数组第i行第j列等于*。否则等于.
贝西有一张她想创作的邮票画，所以农夫约翰借给她一张K×K（1≤K≤N）邮票和一张空的N×N画布。贝西可以将印章顺时针旋转90^∘，并在网格上的任何位置盖章，只要印章完全在网格内。形式上，为了盖章，Bessie选择整数i，j使得i∈[1，N−K+1]和j∈[1、N−K+1]；对于每个（i′，j′），如果邮票在（i′，j′）处有墨水，则1≤i′，j′≤K，画布单元（i+i′−1，j+j′−1）被涂成黑色。贝西可以在冲压之间随时旋转印章。画布单元格一旦涂成黑色，它将保持黑色。
农夫约翰想知道贝西是否有可能用他的邮票创作出她想要的邮票。对于每个T（1≤T≤100）测试用例，帮助Farmer John回答这个问题。
【输入格式】：
输入的第一行包含T，即测试用例的数量。
每个测试用例都以整数N开头，后跟N线条，每一行一个包含*和.的字符串，代表贝西想要的邮票画。
下一行包含K后面是K行，每行包含一个*和.组成的字符串，代表农夫约翰的邮票。
连续的测试用例用换行符分隔。
【输出格式】：
对于每个测试用例，在单独的行上输出“是”或“否”。
【样本输入】：
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∘
旋转90∘
在（1,2）处盖章
在第三个测试用例中，不可能绘制中间单元格。
在第四个测试用例中，Bessie可以执行以下冲压顺序：
旋转90∘
在（1,1）处盖章
在（1,2）处盖章
盖章（2,2）

题目类型~

USACO-2023-铜-2月 

咻咻~

提交答案 状态 返回