PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] UVa 11464 : Even Parity

看板Prob_Solve (計算數學 Problem Solving)作者nicknick0630 (NICK)時間5年前 (2019/04/15 00:30)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/2 (看更多)

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 謝謝各位大大感激不盡 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.183.79 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1555259422.A.7D1.html