题目链接（CF，洛谷） | 强烈推荐博客中观看。

题意

给你一个 n×mn \times m (1≤n,m≤10001 \le n, m \le 1000) 的格点图，每个格子的值要么是 −1-1，要么是 11，现在问你，是否有一条从 (1,1)(1, 1) 到 (n,m)(n, m) 的路径，使得路径上经过的格点的值的和为 00。在路径中，只能从 ai,ja_{i, j} 移动到 ai+1,ja_{i + 1, j} 或是 ai,j+1a_{i, j + 1}（向右或是向下走）。

思路

看到这个 (1≤n,m≤10001 \le n, m \le 1000) 的数据范围就知道暴搜肯定要寄了（别学我），所以得想一些别的办法。

首先，如果经过奇数个格子，或者说 n+m−1n + m - 1 为奇数，那么肯定没有这样的一条路径（经过的 −1-1 和 11 点没有办法相等）。

直接判断某个格子图是否符合要求太麻烦，我们可以思考，如果有任意一条路径，我们是否能根据这条路径的值（也就是途径的格子的和），来做一些改变，最后让路径的值变为 00。

如下图这样就是对路径做了一次改变（改变前后只有一个格子不同）。最后让路径的值产生了变化。
示意图，来自官方题解

在一次改变中，路径的值会产生 −2(−1→1),2(1→−1)-2 (-1 \rarr 1), 2 (1 \rarr -1) 或是 0(1→1OR⁡−1→−1)0 (1 \rarr 1 \operatorname{OR} -1 \rarr -1) 的变化，那么如果我们刚开始的路径值是一个偶数，就可以把这个路径通过这样的改变变为 00 ……吗？

显然是不行的，如果整个格点图全是 −1-1 或是全是 11 就不行，所以我们还得做一些改进。

首先就得确保在这个格点图中不会只有值特别离谱的路径，如果只有值特别离谱的路径，那无论你怎么变，也搞不出值为 00 的路径。

所以我们需要找出值最大的路径，以及值最小的路径。

设值最大的路径的值为 pmax⁡p_{\max}，最小的路径的值为 pmin⁡p_{\min}。

那么如果:

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

我们就一定可以通过这样的变化把任意一个值为偶数的路径变为值为 00 的路径。

或者可以这样理解，如果符合上面那个条件，那我们就可以逐渐把值最小的路径向值最大的路径变换，在这个过程中，一定有一个路径的值等于 00。

至于求这样的格子图的最大和最小路径，就属于是典中典了（用 dp），这里不赘述，如果有不熟悉的可以看洛谷P1004。

代码

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] 的意思是到 i, j 这个点的最大路径的值
        //mn[i][j] 是最小

        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];
        //给 dp 设置边界条件，如果在格子图的左边界，显然只能从上面走过来

        for (int j = 1; j <= m; j++)
            mx[1][j] = mn[1][j] = mn[1][j - 1] + a[1][j];
        //如果在格子图的上边界，只能从左边走过来

        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];
                //经典 dp，选择是从左边走过来还是从上面走过来
            }
        }

        if (mx[n][m] & 1 || mn[n][m] > 0 || mx[n][m] < 0) {
            //mx[n][m] & 1 是判断这个路径是否是奇数的
            //当然也可以直接前面判断 n + m - 1，这样还能快一点
            printf("NO\n");
        } else {
            printf("YES\n");
        }
    }
}