原题链接

题目大意

给定一个$N$行$M$列的矩阵，元素$(i,j)$的取值只可能为$1$或$-1$，现规定从矩阵左上角出发，只能向下或向右移动，最终到达右下角，如下图所示，是否存在一条路径，使得路径上所有元素的值的和为$0$？解答程序只需判断是否存在符合条件的路径，无需求具体路线。

0.png

题目样例

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

output

NO
YES
YES
YES
NO

题解

这道题的难点在于思路，需要发现和综合运用题目的内在性质，涉及到的动态规划只有最基本的数字三角形模型。

根据情景，奇数长度的路径必不可能求和为$0$，对应$N+M$为偶数的情况，其路径长度必为奇数，不可能有合法路径。

注意到存在一种路线的最小修改，每次只可能使总和发生三种改变：$+2$、$0$、$-2$（如下图所示，从图上来看即为将路径上一个元素替换为对角相邻的另一个元素），也就是说，不同路径元素和间的差值一定是$2$的倍数。

1.png

因为存在路线修改的最小操作，任何两条不同路径必然可以通过一系列这种操作互相转化，可以分别求出左上角到右下角路径元素和的最大可能值和最小可能值，其间的值必然只能以$2$为单位连续变化，只需检查其自身和能够变化的路径是否有使元素和为$0$的路径即可。

代码

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
#include<iostream>
#include<algorithm>
#include<cstring>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);
using namespace std;
const int N=1010;

int maxg[N][N],ming[N][N];
int g[N][N];
int t,n,m;

int main(){
    fastIO
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>g[i][j];
            }
        }
        for(int i=1;i<=m;i++){
            maxg[1][i]=g[1][i]+maxg[1][i-1];
            ming[1][i]=g[1][i]+ming[1][i-1];
        }
        for(int i=1;i<=n;i++){
            maxg[i][1]=g[i][1]+maxg[i-1][1];
            ming[i][1]=g[i][1]+ming[i-1][1];
        }
        for(int i=2;i<=n;i++){
            for(int j=2;j<=m;j++){
                maxg[i][j]=max(maxg[i-1][j]+g[i][j],maxg[i][j-1]+g[i][j]);
                ming[i][j]=min(ming[i-1][j]+g[i][j],ming[i][j-1]+g[i][j]);
            }
        }
        int a=maxg[n][m],b=ming[n][m];
        if(a>=0&&b<=0&&maxg[n][m]%2==0) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    return 0;
}