a209. 街友的寒冷夜晚 - 高中生程式解題系統

內容

這已經是古賀離家出走的第四天了，每到夜晚就得忍受街頭 10 度的低溫入眠，古賀再也忍不住這種溫度而去垃圾桶找了幾張破報紙充當棉被，先是草草的抓了幾張大的蓋住身體，但報紙實在是太破碎了，胡亂遮住身體之後還是有冷風從沒蓋住的地方灌入。

古賀想請你算出如何用最少的小塊報紙把風灌入的地方蓋起來 (報紙可以互相重疊)，因為他實在是太冷又太累了。

具體來說，現在有一個 $n \times m$ 的 01 矩陣，如果某個位置是 1，則代表它要被覆蓋，否則不能被覆蓋。請你用最少個數的正方形覆蓋所有的 1，可以重複覆蓋。

輸入說明

有多組測資，每組測資的第一行為正整數 $m, n$。

接下來為一個 $n \times m$ 的 01 矩陣，以 $\text{0 0}$ 作為結尾。

輸出說明

每組數據輸出最少正方形個數

範例輸入 #1

4 3
0 1 1 1
1 1 1 1
1 1 1 1
8 5
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1
0 0

範例輸出 #1

2
6

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 30.0s , <10M

提示：

標籤:

DLX 重複覆蓋問題

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」