作者EdisonX (卡卡獸)
站內Prob_Solve
標題[問題] 一個 block 找出最少可蓋覆方形個數
時間Sun Feb 1 15:16:34 2015
標題有點難想，見諒。
假定有一個地圖，座標可用一個格子表示，長相如下
ＡＢＣＤＥＦＧＨＩ
１□□□□■■■■□
２□□□■■□□■□
３□□■■
■■□■■
４□■■□□■□■■
５□□□□□■□□■
６□□□■■■■■■
紅色點 flood fill 的起始點，
白色點是 flood fill 之結果。
現我想多加一個動作，想用 "
較少 的矩形"，
去包覆這個結果，但苦無較有效率的算法可執行。
我可不需
最少 的矩形 ( 因應 空間/時間 考量問題)，
但目前連 "暴力法" 的想法真的都卡卡的，
不知目前是否已有有效算法可解決？
給個 KEYWORD 也行，謝謝各位。
--
就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮，
永遠當老闆的傀儡 你是不是想這麼做？
是的話你就拿回去~ 拿啊！！
九世宅男 : 下輩子不要再讓我幹工程師了 ~
< Kuso 星爺語錄 >
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1422775009.A.60F.html
1F：→ Morris1028: 要求覆蓋不可重疊，用數個矩形覆蓋所有白色區域？ 02/02 09:32
2F：→ Morris1028: 感覺壓縮算法，如果求最少可以用 DLX 精準覆蓋問題 02/02 09:33
3F：→ Morris1028: 單純找較少，用貪心法，每次找未覆蓋的左上角，往右下 02/02 09:35
4F：→ Morris1028: 盡可能覆蓋最多個數的矩形，直到所有點都被覆蓋。 02/02 09:35
5F：→ EdisonX: 抱歉，沒說清楚，圈出來的每個矩形彼此間可重疊，先感謝 02/02 15:09
6F：→ EdisonX: 您提供的想法，我會先research 02/02 15:09
7F：推 FRAXIS: 矩形可以重疊 那可以覆蓋非白色區域嗎？ 02/03 00:55
8F：→ EdisonX: @FRAXIS, 非白色區域(上圖完全沒上色的) 不能被覆蓋。 02/03 00:57
9F：推 FRAXIS: 那就先找出所有可以使用的矩形 02/03 04:27
10F：→ FRAXIS: 每回合挑一個矩形 使得可以多覆蓋的範圍越多越好 02/03 04:28
11F：推 FRAXIS: 感覺上像是 set cover 的問題 02/03 04:34
12F：→ EdisonX: 最後還是用貪心法先爆出來了，幾個例子效率有點差，謝謝 02/05 02:31
13F：→ EdisonX: 各位。 02/05 02:31