algorithm - 需要的算法：将港口放置在六角地图中以确保洲际旅行

Question

我正在制作一个使用六边形图块来表示地图的游戏；瓦片或十六进制，每个都包含指向其所有邻居的指针，以列表形式。地图可能如下所示：

大的绿色区域是“大陆”，而黄色的小区域是“岛屿”，其余的都是通用水体，请注意，大陆内部可能有少量水。

大陆与海岛始终相邻，互不相接。玩家在任何时候都会占据一个格子。基本移动将玩家从一个格子移动到另一个格子，前提是起点和目的地相邻，并且该移动不会将玩家从陆地格子移动到水格子。

“港口”是一个即将推出的功能，放置在大陆或岛屿的格子中，它们允许玩家从港口移动到任何相邻的水格，这应该可以在陆地之间旅行

问题： 我想在这样的地图中放置至少 2 个港口，以确保玩家始终可以从大陆到岛屿，反之亦然。

由于以下并发症，这比看起来更难：

1. 如果将港口放置在内陆水体的岸边，它们将毫无用处
2. 大陆可能将海洋划分为多个部分，因此港口可能无​​法放置在正确的海岸上（在下面的示例中；H1 和 H2 不能仅通过水进行通信，而 H2 和 H3 可以）

因此，我欢迎任何关于在此类地图上放置港口的合适算法的清晰描述，任何伪代码都将受到高度赞赏

标签： algorithmlanguage-agnosticgraph-theorygraph-algorithm

Answer 1

它是普通 BFS 或双向 BFS。

从接触水的六角开始 BFS - 橙色细胞。如果 BFS 在中间相遇，则在这些陆地区域放置一个港口。这将有助于避免像 H1 港这样的情况，因为像 H1 这样的单元格的 BFS 不会遇到任何其他陆地区域。

注意：在您的帖子中，您不是在寻找要放置的最小港口。同样，BFS 在那里会有所帮助，但是在实施中需要更多的处理。请参阅下面的地图。红色的是地图上的最小港口。