[Solution] Zero Path solution codeforces

Zero Path solution codeforces – You are given a grid with 𝑛n rows and 𝑚m columns. We denote the square on the 𝑖i-th (1𝑖𝑛1≤i≤n) row and 𝑗j-th (1𝑗𝑚1≤j≤m) column by (𝑖,𝑗)(i,j) and the number there by 𝑎𝑖𝑗aij. All numbers are equal to 11 or to 1−1.

Table of Contents

[Solution] Zero Path solution codeforces

You start from the square (1,1)(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 𝑎11a11 and 𝑎𝑛𝑚anm) is 00?

Zero Path solution codeforces

[Solution] Zero Path solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). Description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚10001≤n,m≤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 𝑎𝑖𝑗aij (𝑎𝑖𝑗=1aij=1 or 1−1)  — the element in the cell (𝑖,𝑗)(i,j).

It is guaranteed that the sum of 𝑛𝑚n⋅m over all test cases does not exceed 106106.

Output

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

[Solution] Zero Path solution codeforces

Example
input

Copy
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

[Solution] Zero Path solution codeforces

output

Copy
NO
YES
YES
YES
NO
Note

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

For Solution

Click Here

Leave a Comment