UVa 连结 :
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2459
短网址 : https://is.gd/NYytBw
题目:
给一 N x N 的矩阵，里面每个元素皆为 0 或 1
且每个元素的 parity 定义为该元素位置的上、下、左、右四个位置中 1 的数目
题目要求我们要把其中一些 0 改成 1，让所有元素的 parity 皆为偶数
也就是 0、2、4个，并输出改变次数最少的值 ( 若无法的话输出 -1 )
解法:
列举出第一列，若题目给定的矩阵的第一列无法转换成列举的情况的话，删除此种情况
然后将所有合法的列举情况用第一列推导出第二列
再用 Row 2 推导出 Row 3，依序推导到 Row N
最后再用题目的矩阵与这些列举情况推导出来的矩阵做比较
找出最少 0 转换成 1 的次数
我的问题:
为什么可以保证 Row N 会是正确的? 也就是说 Row N 的 parity 也会是偶数个
若是考虑 Row 1 ~ Row N-1 ，因为都可以用他的下一列来修正
使自己一定为偶数 parity，但是 Row N 不能用 Row N+1 来修正自己
所以想请问要如何证明呢?
这是我写的文章，里面有更清楚的描述，我的问题就是在 "证明" 那一个段落
文章连结 : https://is.gd/eN7WyK
谢谢各位大大
感激不尽