c++ - 如何判断一个单位的士兵是否在网格地图上连接

Question

我正在制作游戏，地图就像网格一样，我有几个单位（每个单位都有几个士兵）。如何判断一个单位的士兵是否连接（连接意味着每个士兵至少有一个方向的来自同一单位的士兵）。地图是网格，相邻单元格是两个，它们可以在 x 和/或 y 处相差 1（除了边界之外的每个单元格都有 8 个相邻单元格，如矩阵）。

Answer 1

您可以在此处使用洪水填充，您的图表是网格的G=(V,E)位置和VE = { (u,v) | there is a soldier in both u and v from the same unit }

基本上，当您将问题简化为该图时，任何图发现算法都可以。从所需单元中的任何士兵调用算法，如果发现算法准确 k发现节点，您可以判断该单元是否“已连接”，k单元中的士兵数量在哪里。

Answer 2

使用联合查找数据结构。测试每一对士兵。每当两个士兵相邻时，他们的等价类就会合并。在对所有此类对进行测试后，如果您最终得到一个等价类，则您的单元已连接。