作者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/cn.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