算法找到难题的解决方案

Question

我正在尝试制作一款游戏，玩家必须在游戏板上从头到尾找到自己的出路。

如您所见，这个游戏板包含一堆红色圆形障碍物。为了赢得比赛，玩家必须移除最少数量的障碍物。所以我的问题是，如何以编程方式找出要移除的最少障碍物，以释放路径？自由路径将被视为圆圈之间的空间，圆圈不重叠且不接触。

所以我真正需要的是要删除的最小圆圈数，我不需要实际路径。有没有简单的方法可以做到这一点？

补充一下对这个棋盘的理解，每个圆圈的半径都是一样的，并且被黑线限制了。

另外，也没有必要直线移动。

Answer 1

这是一个图论最大流问题。

假设每个圆都是图中的一个节点。另外引入 2 个特殊节点:TOP 和 BOTTOM。如果这些节点与 TOP/BOTTOM 侧相交，则将圆与这些节点连接起来。如果圆相交，则将圆对应的节点相互连接起来。

现在您需要在此图中找到最小切割，以TOP 为源 和BOTTOM 为汇，反之亦然。您可以使用 Max-flow_min-cut_theorem解决它。它指出的是 Minimum-cut problem 等同于 Max-flow 问题。您可以在 TopCoder 上找到有关如何解决 Max-Flow 问题 的详细信息.

由于我们只能通过每个节点一次，因此我们应该将节点转换为容量为一的有向边，每个圆具有节点内和节点外。最大流算法将解决结果图上的问题，并考虑到我们正在删除圆圈而不是圆圈之间的连接这一事实。对于这个问题，删除图中的节点而不是边总是更好的决定，因为我们总是可以通过删除节点来删除任何边。另外删除一个节点可能会导致删除多个边。

对了，类似的问题可以在Uva Online Judge上找到.尝试在法官身上解决这个任务是个好主意，然后你会确定你的解决方案是正确的。