CF1360E Polygon
题目描述
Polygon 不仅是开发题目的最佳平台，还是一个边长为 $n$ 的方阵，初始时每个格子都填充字符 0。
在 Polygon 上举行了军事训练。士兵们在第一行的每个格子上方和第一列的每个格子左侧各放置了一门大炮。因此，一共放置了 $2n$ 门大炮。
$n=4$ 时的初始 Polygon。大炮会发射字符 1。任意时刻，最多只有一门大炮在射击。当一个 1 从大炮中射出时，会沿着射击方向一直前进，直到碰到 Polygon 的边界或另一个 1。之后，它会停留在碰撞前的那个格子中，并留在那里。请参考示例以便更好地理解。
更正式地说：
- 如果一门大炮位于第 $i$ 行、第一列左侧，并发射一个 1，那么 1 会从单元格 $(i, 1)$ 开始飞行，并最终停在某个单元格 $(i, j)$；
- 如果一门大炮位于第 $j$ 列、第一行上方，并发射一个 1，那么 1 会从单元格 $(1, j)$ 开始飞行，并最终停在某个单元格 $(i, j)$。
例如，考虑以下射击顺序：
1. 射击第 2 行的大炮。
2. 再次射击第 2 行的大炮。
3. 射击第 3 列的大炮。
你桌上有一份军事训练的报告。这份报告是一个边长为 $n$ 的只包含 0 和 1 的方阵。你想知道训练是否真的发生过。换句话说，是否存在一种射击顺序，使得训练结束后得到给定的矩阵？
每门大炮可以射击任意多次。训练开始前，Polygon 的每个格子都是 0。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是 $t$ 个测试用例。
每个测试用例以一行整数 $n$（$1 \le n \le 50$）开头，表示 Polygon 的大小。
接下来有 $n$ 行，每行长度为 $n$，仅包含 0 和 1，表示训练结束后的 Polygon 方阵。
所有测试用例的矩阵总面积不超过 $10^5$。
输出格式
对于每个测试用例，输出一行：
- 如果存在一种射击顺序可以得到给定矩阵，输出 YES；
- 如果不存在这样的射击顺序，输出 NO。
YES 和 NO 的字母大小写均可。
说明/提示
第一个测试用例在题目描述中已经解释。
第二个测试用例的答案是 NO，因为在 $(1, 1)$ 位置的 1 无论从哪门大炮射出，都会继续向前飞行，不会停在该位置。
由 ChatGPT 4.1 翻译