请提出一个用于解决 Globs 游戏（http://www.deadwhale.com/play.php?game=131）的算法和数据结构。这在极客的视角下相当有趣。

请用 N 表示你的方法的时间-空间复杂度（大O符号），其中 N 是网格的大小 (N>=14)。最好使用复杂度较低的高效算法。

(@MatrixFrog 正确地指出这个游戏也被称为 FloodIt，而 @Smashery 在他下面引用的链接中给出了 3 个月前的解决方案。你们这些只用 1 次前瞻就提出剪枝/贪婪算法的家伙，这会给出次优解。)

该游戏生成一个随机的 nxn 节点正方形网格，其中每个节点被涂成六种颜色之一（绿=1，黄=2，红=3，蓝=4，紫=5，橙=6）。第 1 关有 9×9 网格，然后 n 在每一关都会增加，最高可达 14。
每一关你最多可以走 25 步，否则你就会输。
在每一步中，你选择将左上角的节点更改为哪种颜色，例如 绿->红，这样任何连接的相邻（水平/垂直）的新颜色节点都会被吸收到一个形状中，并且每个被吸收的节点加 1 分到你的分数。
得分目标是用尽可能少的步数完成每个网格，例如，如果你用 16 步完成，那么你剩余的 9 步 => 2*9 倍数乘以你的总累积分数。

显然，有很多方法可以分解这个问题，并且默认选择递归回溯的 14×14 网格是一个可行的竞争者；
还有哪些类型的数据结构适合这个问题？ A* 算法？
不要过于纠结于最优解，我想知道是否存在一个“足够好”的算法。

(我曾想过编写一个机器人并获得极高的分数，这可能是一个有趣的项目。
虽然我只凭自己的大脑就获得了 3.5E+12 的分数。)

回答：

这个游戏真的引起了我的兴趣，所以我花了几天时间来研究它。

我注意到的第一件事是，很容易证明在第一个棋盘之后（在某些情况下可能是 2 个），提高分数的最快方法是使用乘数。因此，我构建了一个系统，目标是用最少的步数解决每个棋盘。我一开始想使用 A* 算法，因为它通常是为这类搜索问题而构建的……但是，这个问题仍然是一个难题。

在讨论 A* 算法时，它的有效性实际上归结为你对启发式估计的选择。你越接近猜测实际距离，为了达到目标需要扩展的节点就越少。对于这个问题，我经历了很多估计的想法，但其中大多数都违反了 A* 规则，即你不能高估实际距离，否则你会破坏 A* 算法的最优性。

但是，有一些方法是可行的。本帖中的其他人已经发布了关于仅将剩余颜色的数量作为估计的想法，这是可接受的，因为它不会高估（对于每个不属于主“洪水”区域的剩余颜色，你必须至少更改一次颜色）。这种启发式算法的问题在于它对实际距离的估计非常差。例如，以第一步为例，通常对颜色的数量进行估计，为 6。它通常扩展为 2 步，每一步通常对颜色数量的估计为 7，依此类推。深入 5 层，对于 10×10 的棋盘大小，大多数叶子的估计值为 11。这种启发式算法基本上是广度优先搜索的实现，直到你到达离目标 4 或 5 步之内。这不是很有效，并且在我自己的测试中，指数在棋盘大小 9 左右运行了很多次，这通常需要在解决方案中大约 14 步。应该注意的是，我的解决方案非常高级，并没有花费太多精力来加速。

问题在于，只有当每一步都对整体解决方案的实际距离进行重大改进时，A* 算法才真正有效。直接查看问题，你可能找不到一种比这更好的启发式算法，而不会高估成本。但是，如果将问题转换为另一个问题，更好的启发式算法就会跳出来。启发式算法“剩余颜色的数量”正在回答一个问题，即剩余可能的最小步数是多少。为了回答这个问题，我问自己“棋盘上哪个位置需要最多的步数才能到达”？我最终确定了“到达右下角需要多少步”作为我的启发式算法。通过运行另一个 A* 搜索（更像查找地图方向），然后计算解决方案中的步数，这很容易实现。我知道在棋盘上选择这是一个任意点，但是在测试中效果很好，并且在我的单处理器测试机上，对每个剩余点运行 A* 算法花费了相当多的时间。

然而，这种启发式算法本身有一种在右下角成为洪水区域的一部分后崩溃的趋势，因此最终结果是 MAX(右下角最小步数，不属于主洪水的剩余颜色数)。这终于能够在我的高级实现中在一秒钟内达到一些非常大的棋盘尺寸。

我将打破记录的任务留给你。