我喜欢玩 Flood-It 益智游戏，可以在线玩:
https://www.lemoda.net/javascript/flood-it/game.html
它也可以作为 iGoogle 小工具使用。目的是用最少数量的连续洪水填充填充整个板。
我正在尝试编写一个程序来以最佳方式解决这个难题。解决这个问题的最佳方法是什么？理想情况下，我想使用 A* 算法，但我不知道估计剩余步数的函数应该是什么。我确实编写了一个程序，该程序进行了深度 4 蛮力搜索以最大化填充区域。它运行得相当好，在解决难题方面击败了我，但我对该算法并不完全满意。
有什么建议吗？提前致谢。
最佳答案
作为一种启发式方法，您可以构建一个图形，其中每个节点代表一组连续的、相同颜色的方 block ，并且每个节点都连接到它所接触的方 block 。 (每条边的权重为 1)。然后，您可以使用寻路算法来计算从左上角到所有其他节点的“距离”。然后，通过查看使用其他 5 种颜色中的每一种颜色进行填充的结果，确定哪一种颜色最小化到“最远”节点的距离，因为这可能是您的瓶颈。
将该计算的结果添加到到目前为止完成的填充数，并将其用作您的 A* 启发式。
关于algorithm - 如何最佳解决洪水填充难题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1430962/