CF1695C Zero Path 题解

Problem Link

Explanation

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

Solution

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

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

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

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

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

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

$$f_{min}, f_{min}+2, \dots,0 , \dots, f_{max}-2, f_{max}$$

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

Core Code

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");
}