The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Problem links: (CF, Luogu) | I strongly recommend reading it on the blog.

Problem Statement

Given an n×mn \times m (1≤n,m≤10001 \le n, m \le 1000) grid, the value of each cell is either −1-1 or 11. Determine whether there is a path from (1,1)(1, 1) to (n,m)(n, m) such that the sum of the values of the cells traversed by the path is 00. On a path, you can only move from ai,ja_{i, j} to ai+1,ja_{i + 1, j} or ai,j+1a_{i, j + 1} (move right or down).

Approach

Seeing the constraint (1≤n,m≤10001 \le n, m \le 1000), we know that brute-force search certainly will not work (do not learn from me), so we need to think of another method.

First, if the path passes through an odd number of cells—in other words, if n+m−1n + m - 1 is odd—then such a path certainly does not exist (the numbers of −1-1 and 11 cells traversed cannot be equal).

Directly determining whether a grid satisfies the requirement is too troublesome. We can instead consider whether, given any path, we can make some changes according to the path’s value (that is, the sum of the cells it passes through) and finally make the path’s value equal to 00.

The figure below shows one change to a path (only one cell differs before and after the change). This ultimately changes the value of the path.
Illustration from the official solution

In one change, the path’s value changes by −2(−1→1)-2 (-1 \rarr 1), 2(1→−1)2 (1 \rarr -1), or 0(1→1OR⁡−1→−1)0 (1 \rarr 1 \operatorname{OR} -1 \rarr -1). Then, if the path’s initial value is even, can we transform the path in this manner into one whose value is 00…?

Obviously not. It does not work if the entire grid consists only of −1-1 or only of 11, so we still need to improve the method.

First, we must ensure that the grid does not contain only paths with especially extreme values. If only paths with especially extreme values exist, no matter how we change them, we cannot produce a path with value 00.

Therefore, we need to find the path with the maximum value and the path with the minimum value.

Let the value of the maximum-value path be pmax⁡p_{\max} and the value of the minimum-value path be pmin⁡p_{\min}.

Then, if:

pmin⁡≤0≤pmax⁡p_{\min} \le 0 \le p_{\max}

we can certainly use such changes to turn an even-valued path into a path whose value is 00.

Alternatively, we can understand it this way: if the condition above holds, we can gradually transform the minimum-value path into the maximum-value path. During this process, there must be a path whose value equals 00.

As for finding the maximum- and minimum-sum paths in such a grid, that is a very standard problem (using DP), so I will not elaborate here. If you are unfamiliar with it, see Luogu P1004.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        int a[n + 1][m + 1]; 
        int mx[n + 1][m + 1], mn[n + 1][m + 1];

        // mx[i][j] means the maximum value of a path to point i, j.
        // mn[i][j] is the minimum.

        memset(a, 0, sizeof(a));
        memset(mx, 0, sizeof(mx));
        memset(mn, 0, sizeof(mn));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }        

        for (int i = 1; i <= n; i++)
            mx[i][1] = mn[i][1] = mx[i - 1][1] + a[i][1];
        // Set the boundary condition for the DP. At the left boundary of the grid, a path can obviously only come from above.

        for (int j = 1; j <= m; j++)
            mx[1][j] = mn[1][j] = mn[1][j - 1] + a[1][j];
        // At the upper boundary of the grid, a path can only come from the left.

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                mx[i][j] = max(mx[i - 1][j], mx[i][j - 1]) + a[i][j];
                mn[i][j] = min(mn[i - 1][j], mn[i][j - 1]) + a[i][j];
                // Standard DP: choose whether to come from the left or from above.
            }
        }

        if (mx[n][m] & 1 || mn[n][m] > 0 || mx[n][m] < 0) {
            // mx[n][m] & 1 determines whether this path has an odd value.
            // Of course, you can also check n + m - 1 directly beforehand, which is slightly faster.
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
}