d009: 習題 Q-1-11. 刪除矩形邊界 — 遞迴 (APCS201910, subtask)
Tags : Recursion
Accepted rate : 119人/127人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-05 16:12

Content

一個矩形的邊界是指它的最上最下列及最左與最右行。

對於一個元素皆為 0 與 1
的矩陣,每次可以刪除四條邊界的其中之一,要以逐步刪除邊界的方式將整個矩陣全
部刪除。刪除一個邊界的成本就是「該邊界上 0 的個數與 1 的個數中較小的」。

 

例如
一個邊界如果包含 3 個 0 與 5 個 1,刪除該邊界的成本就是,刪除該邊界的成本就是 $min(3,5) = 3$。

根據定義,只有一列或只有一行的矩陣的刪除成本是 $0$。不同的刪除順序會導致不同的成本,本題的目標是要找到最小成本的刪除順序。$ 0 < n < 14 $。每格得分數不超過 100。

Input

第一行是兩個正整數 $m$ 和 $n$,以下 $m$ 行是矩陣內容,順序是由上而下, 由左至右,矩陣內容為 01,同一行數字中間以一個空白間隔。$m + n \leq 13$。

Output

最小刪除成本。

Sample Input #1
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
Sample Output #1
1
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 1.0s , <1K
不公開 測資點#1 (20%): 1.0s , <1K
不公開 測資點#2 (20%): 1.0s , <1K
不公開 測資點#3 (20%): 1.0s , <1K
不公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
Recursion
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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