309536: CF1695C. Zero Path

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Zero Path

题意翻译

给你一个 $n \times m$ ($1 \le n, m \le 1000$) 的格点图,每个格子的值要么是 $-1$,要么是 $1$,现在问你,是否有一条从 $(1, 1)$ 到 $(n, m)$ 的路径,使得路径上经过的格点的值的和为 $0$。在路径中,只能从 $a_{i, j}$ 移动到 $a_{i + 1, j}$ 或是 $a_{i, j + 1}$(向右或是向下走)。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

题目描述

You are given a grid with $ n $ rows and $ m $ columns. We denote the square on the $ i $ -th ( $ 1\le i\le n $ ) row and $ j $ -th ( $ 1\le j\le m $ ) column by $ (i, j) $ and the number there by $ a_{ij} $ . All numbers are equal to $ 1 $ or to $ -1 $ . You start from the square $ (1, 1) $ and can move one square down or one square to the right at a time. In the end, you want to end up at the square $ (n, m) $ . Is it possible to move in such a way so that the sum of the values written in all the visited cells (including $ a_{11} $ and $ a_{nm} $ ) is $ 0 $ ? ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1695C/8f2d98d121e7e351eaa9a88e08080da6d06835b5.png)

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10^4 $ ). Description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 1000 $ ) — the size of the grid. Each of the following $ n $ lines contains $ m $ integers. The $ j $ -th integer on the $ i $ -th line is $ a_{ij} $ ( $ a_{ij} = 1 $ or $ -1 $ ) — the element in the cell $ (i, j) $ . It is guaranteed that the sum of $ n\cdot m $ over all test cases does not exceed $ 10^6 $ .

输出格式


For each test case, print "YES" if there exists a path from the top left to the bottom right that adds up to $ 0 $ , and "NO" otherwise. You can output each letter in any case.

输入输出样例

输入样例 #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

说明

One possible path for the fourth test case is given in the picture in the statement.

Input

题意翻译

给你一个 $n \times m$ ($1 \le n, m \le 1000$) 的格点图,每个格子的值要么是 $-1$,要么是 $1$,现在问你,是否有一条从 $(1, 1)$ 到 $(n, m)$ 的路径,使得路径上经过的格点的值的和为 $0$。在路径中,只能从 $a_{i, j}$ 移动到 $a_{i + 1, j}$ 或是 $a_{i, j + 1}$(向右或是向下走)。 由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

Output

**题目大意:**
零路径

给定一个有 $ n $ 行 $ m $ 列的格点图,每个格子的值要么是 $-1$,要么是 $1$。需要判断是否存在一条从 $(1, 1)$ 到 $(n, m)$ 的路径,使得路径上经过的格点的值的和为 $0$。在路径中,每次只能从 $a_{i, j}$ 移动到 $a_{i + 1, j}$ 或 $a_{i, j + 1}$(即只能向右或向下走)。

**输入输出数据格式:**

**输入格式:**
每个测试包含多个测试案例。第一行包含测试案例的数量 $ 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"。每个字母可以以任何大小写形式输出。**题目大意:** 零路径 给定一个有 $ n $ 行 $ m $ 列的格点图,每个格子的值要么是 $-1$,要么是 $1$。需要判断是否存在一条从 $(1, 1)$ 到 $(n, m)$ 的路径,使得路径上经过的格点的值的和为 $0$。在路径中,每次只能从 $a_{i, j}$ 移动到 $a_{i + 1, j}$ 或 $a_{i, j + 1}$(即只能向右或向下走)。 **输入输出数据格式:** **输入格式:** 每个测试包含多个测试案例。第一行包含测试案例的数量 $ 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"。每个字母可以以任何大小写形式输出。

加入题单

上一题 下一题 算法标签: