習題 Q-1-11. 刪除矩形邊界 — 遞迴 (APCS201910, subtask)
Submit solution
分數:
100 (partial)
時間限制:
1.0s
記憶體限制:
1G
作者:
題目類型
允許的語言
Assembly, Brainfuck, C, C++, Python
一個矩形的邊界是指它的最上最下列及最左與最右行。 對於一個元素皆為 0 與 1 的矩陣,每次可以刪除四條邊界的其中之一,要以逐步刪除邊界的方式將整個矩陣全 部刪除。刪除一個邊界的成本就是「該邊界上 0 的個數與 1 的個數中較小的」。 例如 一個邊界如果包含 3 個 0 與 5 個 1,刪除該邊界的成本就是,刪除該邊界的成本就是 \(min(3,5) = 3\)。 根據定義,只有一列或只有一行的矩陣的刪除成本是 \(0\)。不同的刪除順序會導致不同的成本,本題的目標是要找到最小成本的刪除順序。\( 0 < n < 14 \)。每格得分數不超過 100。
輸入格式
第一行是兩個正整數 \(m\) 和 \(n\),以下 \(m\) 行是矩陣內容,順序是由上而下, 由左至右,矩陣內容為 0
或 1
,同一行數字中間以一個空白間隔。\(m + n \leq 13\)。
輸出格式
最小刪除成本。
範例輸入
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
範例輸出
1
評論