Zero Path
Contest: Codeforces Round 801 (Div. 2) and EPIC Institute of Technology Round
Difficulty rating: 1700
Tags: brute force, data structures, dp, graphs, greedy, shortest paths

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$$$?

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
NO
YES
YES
YES
NO

Editorial:
Note that if $$$n+m$$$ is even, then the sum of any path from the top left to bottom right will be odd, and therefore nonzero. So in this case, there is no solution.
Otherwise, every path from top left to bottom right will have even sum. For each position $$$(i, j)$$$ in the grid, we define $$$max_{ij}$$$ to be the maximum possible sum of a path starting at the top left and ending at $$$(i, j)$$$. Similarly, $$$min_{ij}$$$ is defined to be the minimum possible sum starting at the top left and ending at $$$(i, j)$$$. These values can be computed using an $$$O(nm)$$$ DP, where $$$$$$max_{ij} = a_{ij} + max(max_{(i-1)j}, max_{i(j-1)})$$$$$$ $$$$$$min_{ij} = a_{ij} + min(min_{(i-1)j}, min_{i(j-1)})$$$$$$ If $$$0 < min_{nm}$$$ or $$$max_{nm} < 0$$$, there is no path adding up to zero. Otherwise, $$$0$$$ lies in the range $$$[min_{nm}, max_{nm}]$$$, and we can show that there is a valid solution path.
Proof: Let $$$p_1$$$ be a path from $$$(1, 1)$$$ to $$$(n, m)$$$ adding up to $$$min_{nm}$$$, and $$$p_2$$$ be another such path adding up to $$$max_{nm}$$$. Each of these paths consists of $$$n-1$$$ down moves and $$$m-1$$$ right moves, so it can be represented as a string of "R" and "D" of length $$$n+m-2$$$. We can move $$$p_1$$$ to $$$p_2$$$ by a sequence of operations where we swap two adjacent (and different) characters. Visually, what we are doing is replacing one square on the path with a square diagonally adjacent to it. The below picture shows one possible operation on a path.
Note that in each step, the sum of values on the path changes by either $$$-2, 0,$$$ or $$$2$$$. So after performing this sequence of operations taking $$$p_1$$$ to $$$p_2$$$, we have moved the path with sum $$$min_{nm}$$$ to a path with sum $$$max_{nm}$$$, changing the sum by $$$-2, 0, $$$ or $$$2$$$ at each step. Therefore, because both $$$min_{nm}$$$ and $$$max_{nm}$$$ are even, and $$$min_{nm} \leq 0\leq max_{nm}$$$, at some point in this sequence of operations, the sum of the path must be zero.
Complexity: $$$O(nm)$$$