← 返回题目列表

Codeforces · 1695/C

C. 零路径

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

您将获得一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。我们用 $$$(i, j)$$$ 表示第 $$$i$$$-th ($$$1\le i\le n$$$) 行和第 $$$j$$$-th ($$$1\le j\le m$$$) 列上的正方形,并用 $$$a_{ij}$$$ 表示其中的数字。所有数字都等于 $$$1$$$ 或 $$$-1$$$。

您从方格 $$$(1, 1)$$$ 开始,一次可以向下移动一格或向右移动一格。最后,您希望到达$$$(n, m)$$$ 广场。

是否可以以这样的方式移动,使得所有访问过的单元格(包括$$$a_{11}$$$和$$$a_{nm}$$$)中写入的值的总和为$$$0$$$?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) — 网格的大小。

以下 $$$n$$$ 行均包含 $$$m$$$ 整数。第 $$$i$$$ 行上的第 $$$j$$$ 整数是 $$$a_{ij}$$$($$$a_{ij} = 1$$$ 或 $$$-1$$$)— 单元格 $$$(i, j)$$$ 中的元素。

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

输出

对于每个测试用例,如果存在从左上角到右下角总计为 $$$0$$$ 的路径,则打印“YES”,否则打印“NO”。您可以在任何情况下输出每个字母。

示例

输入 #1

5
1 1
1
1 2
1 -1
1 4
1 -1 1 -1
3 4
1 -1 -1 -1
-1 1 1 -1
1 1 1 -1
3 4
1 -1 1 1
-1 1 -1 1
1 -1 1 1

输出 #1

NO
YES
YES
YES
NO

注意

声明中的图片给出了第四个测试用例的一种可能路径。