[問題] 一個 block 找出最少可蓋覆方形個數

[EdisonX (卡卡獸)]

標題有點難想，見諒。

假定有一個地圖，座標可用一個格子表示，長相如下

　ＡＢＣＤＥＦＧＨＩ
１□□□□■■■■□
２□□□■■□□■□
３□□■■■■□■■
４□■■□□■□■■
５□□□□□■□□■
６□□□■■■■■■


紅色點 flood fill 的起始點，
白色點是 flood fill 之結果。

現我想多加一個動作，想用 " 較少 的矩形"，
去包覆這個結果，但苦無較有效率的算法可執行。
我可不需 最少 的矩形 ( 因應 空間/時間 考量問題)，
但目前連 "暴力法" 的想法真的都卡卡的，
不知目前是否已有有效算法可解決？
給個 KEYWORD 也行，謝謝各位。



--
就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮，
永遠當老闆的傀儡   你是不是想這麼做？
是的話你就拿回去~  拿啊！！

九世宅男 : 下輩子不要再讓我幹工程師了 ~
                                          < Kuso 星爺語錄 >

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422775009.A.60F.html
→ Morris1028: 要求覆蓋不可重疊，用數個矩形覆蓋所有白色區域？
→ Morris1028: 感覺壓縮算法，如果求最少可以用 DLX 精準覆蓋問題
→ Morris1028: 單純找較少，用貪心法，每次找未覆蓋的左上角，往右下
→ Morris1028: 盡可能覆蓋最多個數的矩形，直到所有點都被覆蓋。
→ EdisonX: 抱歉，沒說清楚，圈出來的每個矩形彼此間可重疊，先感謝
→ EdisonX: 您提供的想法，我會先research
推 FRAXIS: 矩形可以重疊 那可以覆蓋非白色區域嗎？
→ EdisonX: @FRAXIS, 非白色區域(上圖完全沒上色的) 不能被覆蓋。
推 FRAXIS: 那就先找出所有可以使用的矩形
→ FRAXIS: 每回合挑一個矩形 使得可以多覆蓋的範圍越多越好
推 FRAXIS: 感覺上像是 set cover 的問題
→ EdisonX: 最後還是用貪心法先爆出來了，幾個例子效率有點差，謝謝
→ EdisonX: 各位。