Problem Link

Explanation

给定一个 n×mn \times m 的格点图，每个格子的值为 −1-1 或 11。问题要求判断是否存在一条从起点 (1,1)(1, 1) 到终点 (n,m)(n, m) 的路径，使得路径上经过的格点值的和为 00。路径只能向右或向下移动。

Solution

先上结论。设权值和最大的路径权值为 fmaxf_{max}，最小权值为 fminf_{min}，则如果满足 n+m−1n+m-1 是偶数且 fmin≤0≤fmaxf_{min}\leq 0 \leq f_{max}，那么问题有解。

简单观察样例会发现路径的长度只能是 n+m−1n+m-1，又因为权值只能是 11 或 −1-1，则如果最终有解，11 和 −1-1 的数量应当相等。所以如果路径长度是奇数，必然要输出 NO。

接下来要思考的是路径是怎么从 fminf_{min} 变化到 fmaxf_{max} 的。我们会发现可以通过改变路径转向处的访问位置来变化权值和，一次变化将可能会使权值和改变 +2,−2,0+2,-2,0。

以样例为例，第一次转向时选择 (1,1)→(2,1)(1,1)\to (2,1) 与 (1,1)→(1,2)(1,1)\to (1,2) 不会对结果造成影响。而第二次转向时，选择 (1,2)→(2,2)(1,2)\to (2,2) 会比 (1,2)→(1,3)(1,2)\to (1,3) 的权值和多 22。

又因为路径的长度限制了为偶数，也就是说 11 和 −1-1 的数量要么都是偶数，要么都是奇数。这两种情况都会使得权值和为偶数，也就是 fminf_{min} 和 fmaxf_{max} 都是偶数。

那么就可以看看权值和是怎么从最小值变化为最大值的了。因为我们限定了奇偶性和变化规律，所以其变化序列必将是：

fmin,fmin+2,…,0,…,fmax−2,fmaxf_{min}, f_{min}+2, \dots,0 , \dots, f_{max}-2, f_{max}

一定会在变化过程中经过权值和为 00 的情况，所以结论得证。

Core 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

T=read();
while(T--)
{
	n=read();m=read();
	for(int i=0;i<=n;i++) minn[i][0]=INF,maxn[i][0]=-INF;
	for(int i=0;i<=m;i++) minn[0][i]=INF,maxn[0][i]=-INF;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=read();
		}
	}
	if((n+m-1)%2==1)
	{
		printf("NO\n");
		continue;
	}
	minn[1][1]=maxn[1][1]=a[1][1];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i!=1 || j!=1)
			{
				maxn[i][j]=max(maxn[i-1][j],maxn[i][j-1])+a[i][j];
				minn[i][j]=min(minn[i-1][j],minn[i][j-1])+a[i][j];
			}
		}
	}
	if(maxn[n][m]>=0 && minn[n][m]<=0) printf("YES\n");
	else printf("NO\n");
}