题解

思路

任意路径经过的格子数恒为 $n+m-1$。若该数为奇数，若干个 $\pm1$ 的和不可能为 $0$，可以直接输出 NO。

对每个格子分别维护从起点到这里的最小路径和与最大路径和。由于每个格子的值只有 $-1$ 和 $1$，所有可达路径和具有相同奇偶性，并且介于最小值与最大值之间的同奇偶整数都可以达到。因此，在路径长度为偶数时，只需判断终点是否满足

做法

令 low[i][j] 和 high[i][j] 分别为到达 $(i,j)$ 的最小与最大路径和，从上方或左方状态转移并加上当前格子的值。最终结合路径长度奇偶性判断。

极小网格可以 DFS 枚举所有单调路径；中等网格可以为每个格子保存所有精确可达和；满分算法只保留两个极值。

正确性证明

最小/最大 DP 显然分别枚举了最后一步来自上方或左方的所有路径，因此终点极值正确。

每条路径长度相同，故所有路径和奇偶性相同。将一条单调路径逐步变形为另一条时，每次只交换一个局部的“右下”与“下右”，路径和变化为 $-2,0$ 或 $2$。因此在最小和最大路径之间不会缺失具有正确奇偶性的值。

若路径长度为奇数，零的奇偶性不符，不存在答案；否则零的奇偶性正确，且当且仅当它位于终点最小值和最大值之间时可达。算法的判断因此充要。

复杂度分析

时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。