切換
舊版
前往
大廳
主題

ZeroJudge - b005: 布林矩陣的等價短陣 解題心得

Not In My Back Yard | 2018-10-09 12:05:06 | 巴幣 0 | 人氣 540

題目連結:


題目大意:
給定一正整數N(N < 100),表示有一 N x N 的01矩陣(布林矩陣)。接下來有N列,每列有N個數字,代表其陣列的內容。

並定義:當矩陣的每一列的和與每一行的和皆為偶數時,稱此矩陣為等價矩陣。

以下為一4 x 4等價矩陣:
1010
0000
1111
0101

求給定的矩陣是否等價,是的話請輸出:「OK」;反之,如果可以經由改變一個數字,便成為等價,則輸出:「Change bit 」以及改變的數字位置;再不然,輸出:「Corrupt」。

註:是的,題目標題有錯字。


範例輸入:
4
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 0 1 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 1 1 0
1 1 1 1
0 1 0 1


範例輸出:
OK
Change bit (2,3)
Corrupt



解題思維:
這題不難,直接用迴圈跑過每一列、每一行,紀錄哪些行列的和是奇數。

如果,沒有人是奇數,當然就是「OK」的情形。

反之,我們可以觀察到如果只有某一列及某一行的和為奇數,那我們就可以藉由改變那一列與那一行的交點上的數字,使其成為等價。因此是「Change bit 」的情形。

如果,有多列、多行為奇數,則是「Corrupt」。無法只經由改變一個數字就變成等價。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作