Zero Path
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$$$?
One possible path for the fourth test case is given in the picture in the statement.
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.
for case in range(int(input())):
    (n, m) = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    if (n + m - 1) % 2:
        print('NO')
        continue
    dp = [0] * (m + 1)
    for i in range(n):
        dp[0] = int(not i)
        for j in range(m):
            dp[j + 1] = (dp[j] | dp[j + 1]) << (a[i][j] == -1)
    if dp[-1] & 1 << (n + m - 1) // 2:
        print('YES')
    else:
        print('NO')
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    a = [list(map(int, input().split())) for i in range(n)]
    if (n + m) % 2 == 0:
        print('NO')
    else:
        g = [[0] * m for i in range(n)]
        g[0][0] = 1 << (a[0][0] == -1)
        for j in range(1, m):
            g[0][j] = g[0][j - 1] << (a[0][j] == -1)
        for i in range(1, n):
            g[i][0] = g[i - 1][0] << (a[i][0] == -1)
            for j in range(1, m):
                g[i][j] = (g[i - 1][j] | g[i][j - 1]) << (a[i][j] == -1)
        if g[n - 1][m - 1] & 1 << (n + m - 1) // 2 == 0:
            print('NO')
        else:
            print('YES')
for case in range(int(input())):
    (n, m) = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    if (n + m - 1) % 2:
        print('NO')
        continue
    dp = [0] * (m + 1)
    for i in range(n):
        dp[0] = int(not i)
        for j in range(m):
            dp[j + 1] = (dp[j] | dp[j + 1]) << (a[i][j] == -1)
    if dp[-1] & 1 << (n + m - 1) // 2:
        print('YES')
    else:
        print('NO')