/ Vijos / 题库 /

印章网格

印章网格

时间限制: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**

信息

ID
2829
难度
(无)
分类
搜索 | 枚举模拟 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者