d082: P-6-21. 刪除邊界 (APCS201910)
Tags : DP
Accepted rate : 147人/161人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-07 11:07

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
測資資訊:
記憶體限制: 64 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 :

 $0 < m, n < 30$

Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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