d090. P_6_21 刪除邊界 (APCS201910)
Tags : ch6
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-04-16 22:44

Content

一個矩陣的第一列與最後一列以及第一行與最後一行稱為該矩陣的四條邊界線,如果某一條邊界線的內容都是相同元素,則可以刪除該邊界線。如果一條邊界線的內容不完全相同,你可以修改某些格子的內容讓邊界線的內容變成相同後,再刪除該邊界線。

矩陣在刪除一條邊界線後,還是一個矩陣,但列數或行數會減少一,本題的目標是重複執行修改與刪除邊界的動作,最後將整個矩陣刪除。

輸入一個 0/1 矩陣,請計算最少要修改多少個元素才能將整個矩陣刪除。請注意:根據定義,只有一列或是只有一行的矩陣可以不需要任何修改就可以被全部刪除。

Input

第一行為兩個不超過 $25$ 的正整數 $m$ 和 $n$,以下 $m$ 列 $n$ 行是矩陣內容,順序是由上而下,由左至右,矩陣內容為 $0$ 或 $1$,同一行數字中間以一個空白間隔。

Output

 最少修改次數。

Sample Input #1
4 5
0 1 0 1 1
1 1 1 0 1
0 0 0 0 0
0 0 0 1 0
Sample Output #1
2
Sample Input #2
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
Sample Output #2
1
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1K
Hint :

範例一說明:刪除最後一列(修改1成0,成本1),刪除最後一列(成本0),刪除最後一列(修改一個1,成本1),成本總和2。
範例二說明:刪除最右行(修改1個1,成本1),刪除最右行(成本0),刪除第一列(成本0),修改最後一列(成本0),總和1。

Tags:
ch6
出處:
Prof. Wu [管理者: ktlai (K.我已霸榜.Tlai) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」