回『AP325題庫』
e027: 刪除矩形邊界 — 遞迴
Tags :
Accepted rate : 4人/5人 ( 80% ) [非即時]
評分方式：
Tolerant

最近更新 : 2023-12-28 19:50

Content

一個矩形的邊界是指它的最上與最下列以及最左與最右行。對於一個元素皆為 0 與 1 的矩陣, 每次可以刪除四條邊界的其中之一, 要以逐步刪除邊界的方式將整個矩陣全部刪除。刪除一個邊界的成本就是「該邊界上 0 的個數與 1 的個數中較小的」。例如一個邊界如果包含 3 個 0 與 5 個 1, 刪除該邊界的成本就是 min{3,5} = 3。根據定義, 只有一列或只有一行的矩陣的刪除成本是 0。不同的刪除順序會導致不同的成本, 本題的目標是要找到最小成本的刪除順序。

Input

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

Output

最小刪除成本。

Sample Input 
3 5
0 0 0 1 0
1 0 1 1 1
0 0 0 1 0
Sample Output 
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 ：

將目前的矩陣範圍當作遞迴傳入的參數, 對四個邊界的每一個, 遞迴計算刪除該邊界後子矩陣的成本, 對四種情形取最小值, 遞迴的終止條件是: 如果只有一列或一行則成本為 0。(本題有更有效率的 DP 解法)

Tags:
出處:
AP325 [管理者：
Eason0165 (EasonLearner)
]

Status Forum 排行

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