收集一个圆的中心,这个圆将“环绕”更高数量的生物。

我会在这里主要讲理论,因为这个上下文很难解释。

我有一个14x17的画布,在这个画布上有随机的生物,每个生物只能占据一个正方形,我在一个表格中有所有生物的坐标。

我有一颗"炸弹",当我点击我想要它爆炸的格子时,它会在我点击的位置产生爆炸。

这是实际的炸弹: 冰爆炸

因此,考虑到炸弹来自我所坐落的画布中心,周围有随机数量的生物,我该如何找到最佳的投弹位置,以覆盖最多的生物?

(如果只能击中最少量的生物才投掷,可以得到奖励分数)。

点赞
用户844416
用户844416

算法方法 - 找到给定半径覆盖最多生物的圆的中心点。我认为这样的算法(如果存在)相当复杂( [示例](http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf),[另一个示例](https://cs.stackexchange.com/questions/1825/maximum-enclosing-circle-of-a-given-radius)),对于这个相对较小的领域大小来说有些过度。

Brutforce算法 - 计算所有可能圆内部的生物数量

逆算法 - 需要在生物移动过程中持续工作 - 保持整数数组 - 每个元素是从此点可到达的生物数。当生物向右移动时,递减左侧单元格,递增右侧单元格等。例如,对于在(2,3)和(4,3)坐标中的两个生物。 (3,3)点是最好的投掷地点。

0 0 1 0 0
0 1 1 1 0
0 0 2 0 1
0 1 1 1 1
0 0 1 1 1

哪种方法更好 - 取决于某些条件 - 生物是否经常移动?等等。

2014-05-07 04:40:53