← 返回题目列表

Codeforces · 1579/C

C. 蜱虫

中文机器翻译题面 查看原题

卡西米尔有一张矩形纸,上面有一个大小为 $$$n \times m$$$ 的格子区域。最初,视野中的所有单元格都是白色的。

让我们用 $$$(i, j)$$$ 表示垂直坐标 $$$i$$$ 和水平坐标 $$$j$$$ 的单元格。左上单元格将被称为 $$$(1, 1)$$$,右下单元格将被称为 $$$(n, m)$$$。

卡西米尔在场上画了不同大小的蜱虫。大小为 $$$d$$$ ($$$d > 0$$$) 且其中心位于单元格 $$$(i, j)$$$ 中的刻度绘制如下:

1. 首先,将中心单元 $$$(i, j)$$$ 涂成黑色。
2. 然后,左上角对角中心的 $$$d$$$ 个单元格和右上角对角中心的 $$$d$$$ 个单元格也被涂成黑色。
3. 即绘制 $$$0$$$ 和 $$$d$$$ 之间所有 $$$h$$$ 坐标为 $$$(i - h, j \pm h)$$$ 的所有单元格。特别是,一个刻度由 $$$2d + 1$$$ 黑色单元格组成。

如果再次绘制,已绘制的单元格将保持黑色。下面您可以找到 $$$4 \times 9$$$ 框的示例,其中有两个尺寸为 $$$2$$$ 和 $$$3$$$ 的刻度。

为您提供了大小为 $$$n \times m$$$ 的方格字段的描述。卡西米尔声称这个字段是在他在上面画了一些(可能是 $$$0$$$)勾号后出现的。刻度可以具有不同的大小,但每个刻度的大小至少为 $$$k$$$ (即,所有刻度的 $$$d \ge k$$$)。

确定该字段是否确实可以通过绘制一些(可能没有)大小为 $$$d \ge k$$$ 的刻度来获得。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

以下行包含测试用例的描述。

测试用例描述的第一行包含整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 10$$$; $$$1 \le m \le 19$$$) — 字段大小和卡西米尔绘制的刻度的最小大小。以下 $$$n$$$ 行描述该字段:每行由 $$$m$$$ 字符组成,可以是“.”如果相应的单元格尚未绘制,否则为“*”。

输出

打印 $$$t$$$ 行,每行包含相应测试用例的答案。如果可以通过绘制至少给定大小的刻度来获得给定字段,则测试用例的答案应该为“是”,否则为“否”。

您可以按照您想要的任何大小写打印每个字母(例如,字符串 yEs、yes、Yes 和 YES 都将被识别为肯定答案)。

示例

输入 #1

8
2 3 1
*.*
...
4 9 2
*.*.*...*
.*.*...*.
..*.*.*..
.....*...
4 4 1
*.*.
****
.**.
....
5 5 1
.....
*...*
.*.*.
..*.*
...*.
5 5 2
.....
*...*
.*.*.
..*.*
...*.
4 7 1
*.....*
.....*.
..*.*..
...*...
3 3 1
***
***
***
3 5 1
*...*
.***.
.**..

输出 #1

NO
YES
YES
YES
NO
NO
NO
NO

注意

第一个示例测试用例由两个星号组成,两个星号都不能是独立的刻度,因为大小为 $$$0$$$ 的刻度不存在。

第二个示例测试用例已在声明中描述(检查声明中的图片)。该字段可以通过绘制大小为 $$$2$$$ 和 $$$3$$$ 的刻度来获得,如图所示。

第三个示例测试用例中的字段对应于大小为 $$$1$$$ 的三个刻度。它们的中心单元格标有 $$$\color{blue}{\text{blue}}$$$、$$$\color{red}{\text{red}}$$$ 和 $$$\color{green}{\text{green}}$$$ 颜色: *.*.*$$$\color{蓝色}{\textbf{*}}$$$**.$$$\color{绿色}{\textbf{*}}\color{红色}{\textbf{*}}$$$.....

第四个示例测试用例中的字段可以通过绘制两个大小为 $$$1$$$ 和 $$$2$$$ 的刻度来获得。它们的顶点分别用 $$$\color{blue}{\text{blue}}$$$ 和 $$$\color{red}{\text{red}}$$$ 颜色标记如下:.....*...*.*.*...$$$\color{red}{\textbf{*}}$$$.*...$$$\color{blue}{\textbf{*}}$$$。

无法获取第五个示例测试用例中的字段,因为 $$$k = 2$$$,并且从上数第四行坐标为 $$$(4, 5)$$$ 的最后一个星号只能是大小为 $$$1$$$ 的刻度的一部分。

无法获取第六个示例测试用例中的字段,因为左上角的星号 $$$(1, 1)$$$ 不能是独立的刻度,因为刻度的大小必须为正,并且不能是最后一行中心单元格的刻度的一部分,因为它与 $$$(2, 2)$$$ 中的中间单元格通过间隙(点,“.”)分隔开。

在第七个示例测试用例中,类似地,无法通过所描述的过程获取该字段,因为坐标为 $$$(1, 2)$$$(第一行中的第二个单元格)、$$$(3, 1)$$$ 和 $$$(3, 3)$$$(底部最左边和最右边的单元格)的星号不能是任何刻度的一部分。