题目描述

《超级马里奥制造》是为了纪念《超级马里奥》系列 30 周年而制作的作品。《超级马里奥制造》的最大特点是整个游戏包含一个完整的关卡编辑系统，允许玩家使用 Wii U GamePad 设计和创建马里奥关卡；玩家还可以将自己设计的关卡上传到任天堂的服务器，与全球玩家分享。

作为《超级马里奥》的忠实玩家，你创建一个"气球关卡"！这个关卡可以视为一个有限大小的网格，其中一些单元格包含无法通行的障碍物，例如尖刺。玩家需要控制"气球马里奥"从网格的第一列移动到最后一列，通过相邻的单元格并避免尖刺等障碍物。作为一款横向卷轴游戏，其独特之处在于有限的视野，超出可见范围的区域是无法到达的。这一设定对合理的关卡设计提出了重大挑战：即使对于非常聪明的玩家，视野的限制也可能导致他们进入"死胡同"，无法完成关卡。在这个问题中，你需要确定你设计的关卡中是否存在这种现象。

在这个问题中，我们将考虑以下简化模型。一个关卡将被视为一个大大小为 $N \times M$ 的网格，"气球马里奥"角色从 $(1,1)$ 开始，玩家的目标是将"气球马里奥"操控到 $(1,M)$。一些单元格包含障碍物，而"气球马里奥"角色无法通过这些单元格。第一列和最后一列没有放置障碍物。当"气球马里奥"角色位于 $(X,Y)$ 时，玩家的视野为 $\{(U,V) | 1 \leq U \leq N, Y \leq V \leq \min(Y + K,M)\}$，这意味着玩家可以看到这些单元格中是否有障碍物。当"气球马里奥"角色位于 $(X,Y)$ 时，角色可以向 $(X+1,Y)$ 上移，向 $(X-1,Y)$ 下移，或向 $(X,Y+1)$ 右移，只要目标单元格在地图边界内且不包含障碍物。

你需要确定是否存在一条从起点 $s_0 = (1,1)$ 到某个点 $s_\ell = (X,Y)$ 的路径，使得以下条件同时满足：

1. "气球马里奥"可以沿着路径 $P = s_0s_1 \ldots s_\ell$ 从 $s_0$ 移动到 $s_\ell$。
2. 对于任何 $1 \leq i \leq \ell$，玩家无法根据在 $s_{i-1}$ 的可见信息排除从 $s_i$ 到达 $(1,M)$ 的可能性。
3. 然而，玩家无法从 $s_\ell$ 将"气球马里奥"移动到 $(1,M)$。

输入格式

输入的第一行包含一个正整数 $T (1 \leq T \leq 10^4)$，表示测试用例的数量。每个测试用例描述如下。

每个测试用例的第一行包含三个正整数 $N,M,K (2 \leq N,M,N \cdot M \leq 10^6, 1 \leq K \leq M - 1)$，表示地图的大小参数和可见范围参数。接下来的 $N$ 行每行包含一个长度为 $M$ 的二进制字符串 $s_i$，表示地图第 $i$ 行的障碍物信息。这里，$s_{i,j} = 1$ 当且仅当在位置 $(i,j)$ 有障碍物。输入保证第一列和最后一列没有障碍物，并且从 $(1,1)$ 到 $(1,M)$ 存在一条路径。

保证所有测试用例中 $N \cdot M$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，如果存在满足问题中所求条件的路径，则在一行中输出 是（不带引号）；否则，输出 否（不带引号）。评估不区分大小写，即 YES、yes、Yes 等都被接受。

6
3 5 2
00010
01110
00000
3 5 3
00010
01110
00000
3 5 2
01000
01110
00000
3 5 2
00000
01110
00000
3 5 2
01010
01110
00000
5 5 2
00000
00110
00010
01010
00010

Yes
No
No
No
No
Yes

解释 #1

对于第一个测试样例，玩家在 $(1,1)$ 的可见信息可以表示为以下矩阵：

000??  
011??  
000??

根据这些信息，玩家无法排除从 $(1,2)$ 到达 $(1,5)$ 的可能性。然而，"气球马里奥"无法从 $(1,2)$ 移动到 $(1,5)$。

对于其他测试样例（最后一个除外），玩家不会因为视野限制而遇到无法到达终点的死胡同。