印章网格
时间限制:1秒 内存限制:256M
【题目描述】
印章画是在 \(N×N\) 格子的画布上的黑白画,其中某些单元格涂上了墨水,而其他单元格是空白的。它可以用 \(N×N\) 的字符数组来描述。如果画布的某方格内有墨水,那么数组中对应的第 \(i\) 行第 \(j\) 列元素为 '* ' ,否则为 '.' 。
贝西想创作一幅印章画,因此农夫约翰借给了她一个 \(K×K(1 ≤ K ≤ N)\) 大小的印章和一张 \(N×N\) 空白画布。贝西可以将印章顺时针旋转 90 度,而且只要印章完全落在画布的网格内,她就可以在画布上的任何地方盖章。正式地讲就是,在盖章时,B贝西会选择两整数 \(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 (1 ≤ T ≤ 100)\)组数据中的每一组,帮助农夫约翰求出问题的答案。
【输入格式】
输入的第一行包含 \(T\),即测试数据的数量。
每个测试数据以一个整数 \(N\) 开始。后面跟着 \(N\) 行,每一行包含一个由 * 和 . 组成的字符串,表示贝西想要绘制的印章画。接下来一行是 \(K\)。之后跟着 \(K\) 行,每一行包含一个 * 和 . 组成的字符串,代表农夫约翰的印章。
每一个连续的测试用例之间用换行符分隔。
【输出格式】
对于每一个测试数据,在单独的行上输出“YES”或“NO”。
【输入输出样例】
Input
4
2
**
*.
1
*
3
.**
.**
***
2
.*
**
3
...
.*.
...
3
.*.
...
...
3
**.
.**
..*
2
.*
*.
Output
YES
YES
NO
YES
【样例说明】
在第一个测试用例中,贝西可以执行以下盖章顺序:
1、在(1, 1)处盖章
2、在(1, 2)处盖章
3、在(2, 1)处盖章
在第二个测试用例中,Bessie可以执行以下盖章顺序:
1、 在 (2, 2) 处盖章
2、 在 (2, 1) 处盖章
3、 旋转 90度
4、 旋转90度
5、 在(1, 2) 处盖章
在第三个测试用例中,无法绘制中间的单元格。
在第四个测试案例中,Bessie可以执行以下的盖章顺序:
1、 旋转 90度
2、 在(1, 1)处盖章
3、 在(1, 2)处盖章
4、 在(2, 2)处盖章
【数据限制】
对于 \(100\%\) 的数据,\(1≤N≤20\)
【来源】
Mr.he**