Makerlife 的小站
·
CF1695C Zero Path 题解
💡
原文中文，约1300字，阅读约需4分钟。
📝
内容提要
给定一个n×m的格点图，判断是否存在一条从起点到终点的路径，使得路径上经过的格点值的和为0。路径只能向右或向下移动。根据路径长度和权值的奇偶性，可以判断问题是否有解。路径的权值和会在最小值和最大值之间变化，且一定会经过权值和为0的情况。
🎯
关键要点
- 给定一个 n × m 的格点图，判断是否存在一条路径使得路径上经过的格点值的和为0。
- 路径只能向右或向下移动。
- 如果路径长度 n + m - 1 是偶数且最小权值 fmin ≤ 0 ≤ 最大权值 fmax，则问题有解。
- 路径长度为奇数时，必然输出 NO。
- 路径的权值和可以通过改变路径转向处的访问位置来变化，变化可能导致权值和改变 +2, -2, 0。
- 路径的长度限制使得 1 和 -1 的数量要么都是偶数，要么都是奇数，权值和为偶数。
- 权值和的变化序列必将经过权值和为0的情况，因此结论得证。
➡️
