如何快速找到最佳炸弹落差区？

Question

我得到了一个类似这样的功课:

您将获得一个由四种颜色的像素组成的图像.颜色对应于地形,敌人,盟友和墙壁.可以在任何坐标(一对整数)处放下炸弹.你也得到了:

• r - 炸弹的效果半径(以像素为单位,正整数)
• e - 杀死敌人的点数
• a - 杀死盟友的点数

(例如r = 10,e = 1,a = -2)

当炸弹落下时,半径(欧几里德距离)内的所有敌人和盟友都会被杀死,除非他们和炸弹之间有一堵墙(即连接士兵和炸弹的非抗锯齿线穿过墙壁).当炸弹落在墙上时,这个特定像素就像普通地形一样.墙的其余部分仍然是墙.

你的得分是0开始.找到你应该丢弃一颗炸弹以获得最佳分数的坐标.如果有多个最佳解决方案,请返回其中任何一个.

这是一个示例图像裁剪,调整大小并改变颜色以提高可读性:

我可以在这里找到原始图像.

我已经解决了什么

我知道强行解决这个问题是一个可怕的解决方案.我想出了如何在没有墙壁的情况下快速解决问题.这是一些伪代码:

args Map, R, A, E

for (every Soldier)
    create a Heightmap with dimensions of Map
    zero-fill the Heightmap
    on the Heightmap draw a filled circle of value 1 around Soldier with radius R

    if (Soldier is Ally)
        multiply Heightmap by A
    else
        multiply Heightmap by E

add all Heightmaps together
return coordinates of highest point in TotalHeightmap

当然,这个"片段"可以进行优化,但在这种形式下更容易理解.通过用墙壁约束高度图圆圈,它可以扩展到完整的解决方案.绘制圆圈很简单,许多图像处理库提供了执行此操作的功能,因此绘制圆形,然后在墙上绘制墙壁以及从中心停止在墙壁或圆形边界上的填充圆圈可能是个好主意.我将在实施时检查性能.

没有约束圈我会这样做:

run the above code to get a TotalHeightmap
create empty PointList

for (every Point in TotalHeightmap)
    create PointObject with properties:
        Coordinates,
        Height,
        WallsFlag = False
    add PointObject to PointList

sort PointList by descending Height

until (PointList[0].WallsFlag == True)
    for (every Soldier in radius R from PointList[0])
        if (Bresenham line connecting Soldier with PointList[0] intersects a Wall)
            subtract (A if Soldier is Ally else E) from PointList[0].Height

    set PointList[0].WallsFlag = True
    sort PointList by descending Height

return PointList[0].Coordinates

只要敌人和盟友的分数都是非负的,它就会起作用,所以它远非完美.为了解决这个问题,我可以遍历所有像素,但这会非常慢(不像蛮力那么慢,我猜,但这听起来不是一个好主意).寻找墙壁交叉点的方法似乎也很粗糙.

我正在寻找一个更优雅,更快速的解决方案来解决这个问题.你会如何解决它？如果有帮助的话,我将用PIL在Python中实现它.

顺便说一下,我相信我的老师很好,我在SO上发布这个问题,我相信他甚至希望我讨论并实施最佳解决方案.

---

Answer 1

这是一个部分答案,我希望能引发一些讨论:

解决任何问题的第一条规则是找到一个更容易的问题.在这种情况下,我们可以问:

如果没有墙壁,什么是好的解决方案？

并进一步减少到

如果没有墙壁或敌人,什么是好的解决方案？

甚至更进一步,

如果没有墙壁或敌人并且炸弹的半径为1,那么什么是一个很好的解决方案呢？

这相当于说

给定一组点,定位单位磁盘以覆盖可能的最大点数.

凉.这感觉就像一个很好的,坚实的,与领域无关的问题,许多人肯定会遇到过这个问题.一些快速的谷歌搜索和wahey,我们发现了相当多的相关资源,包括这个SO问题.

在那个问题中,接受的答案是一个重要的观察:如果我们有一个覆盖最大点数的磁盘,我们可以移动该磁盘以获得另一个磁盘,其边缘至少有两个点.因此,如果我们在彼此的距离2内取每一对点并通过该对点构建两个单位圆(对于整体的O(n ^ 2)个圆),则保证这些圆中的一个包含最大数量的点可能.

这可以很容易地适应您的问题的"无墙"版本.虽然它天真地是O(n ^ 3)(可能是O(n ^ 2)个圆圈,并且每个圆圈内可能有n个点),但它可能比典型问题实例中的快得多.如果你想要聪明一点,看看固定半径最近邻问题(我能找到的最好的论文在这里,但遗憾的是没有公开版).

我们怎么能介绍墙呢？如果圆盘与墙壁相交,我们无法可靠地移动它,使得两个点位于边缘上,同时保持相同的分数.我会考虑一下,希望其他人在此期间会有一些想法.

精神测试任何候选算法的三种情景:

1. 当地图上有单个"像素"墙时,找到在单位距离和视线范围内同时最大化点数的位置.

2. 当地图上有单个直墙时,找到在单位距离和视线范围内同时最大化点数的位置.

3. 当墙壁在地图上形成单个空心方形时,找到在单位距离和视线范围内同时最大化点数的位置.