Zero Path (Codeforces 1695C)
Tags: 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: 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: 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.

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

Sample Inputs:
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

Sample Outputs:
NO
YES
YES
YES
NO

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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')