← 返回题目列表

Codeforces · 1360/E

E. 多边形

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

多边形不仅是解决问题的最佳平台,而且是边长为 $$$n$$$ 的方阵,最初填充字符 0。

多边形上,举行了军事训练。士兵们在第一行每个牢房上方放置一门大炮,在第一列每个牢房左侧放置一门大炮。因此,总共放置了$$$2n$$$大炮。

$$$n=4$$$ 的初始多边形。

大炮射击角色 1. 在任何时刻,只有一门大炮正在射击。当 1 从大炮中飞出时,它会向前飞行(沿射击方向),直到与多边形边界或另一个 1 发生碰撞。之后,它会选取碰撞前所在的单元格并保留在那里。查看示例以更好地理解。

更正式地说:

- 如果一门大炮站在第一列左侧的 $$$i$$$ 行中,并以 1 进行射击,则 1 从单元格 ($$$i, 1$$$) 开始飞行,并在某个单元格 ($$$i, j$$$) 结束;
- 如果一门大炮站在第一行上方的 $$$j$$$ 列中,并以 1 进行射击,则 1 从单元格 ($$$1, j$$$) 开始飞行,并在某个单元格 ($$$i, j$$$) 中结束。

例如,考虑以下镜头序列:

1. 射击$$$2$$$行中的大炮。                         2. 射击$$$2$$$行中的大炮。                         3. 发射$$$3$$$栏中的大炮。

你的桌子上有一份军事训练的报告。该报告是一个边长为 $$$n$$$ 的方阵,由 0 和 1 组成。您想知道训练是否真的发生过。换句话说,是否存在一系列镜头,以便在训练后获得给定的矩阵?

每门大炮可以进行任意数量的射击。训练之前,多边形的每个单元格都包含 0。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含整数 $$$n$$$ ($$$1 \le n \le 50$$$) 的行开始 — 多边形的大小。

接下来是长度为 $$$n$$$ 的 $$$n$$$ 行,由 0 和 1 组成 - 训练后的多边形矩阵。

一次测试中所有测试用例的矩阵总面积不超过$$$10^5$$$。

输出

对于每个测试用例打印:

- 如果存在导致给定矩阵的一系列镜头,则为“是”;
- 如果这样的序列不存在,则为“否”。

YES 和 NO 中的字母在任何情况下都可以打印。

示例

输入 #1

5
4
0010
0011
0000
0000
2
10
01
2
00
00
4
0101
1111
0101
0111
4
0100
1110
0101
0111

输出 #1

YES
NO
YES
YES
NO

注意

第一个测试用例在声明中进行了解释。

第二个测试用例的答案是否定的,因为从任何大炮中飞出的单元格中的 1 ($$$1, 1$$$) 都会继续飞行得更远。