如何判断一个单位的士兵在网格地图上是否相连？
如何判断一个单位的士兵在网格地图上是否相连？
提问于 2012-08-06 21:41:13
我正在制作游戏和地图，就像网格一样，我有几个单位(每个单位都有几个士兵)。如何判断来自一个单位的士兵是否连接(连接是指每个士兵至少有一个来自同一单位的一个方向的士兵)。Map是网格，相邻单元是两个可以在x和/或y处仅相差1的单元(除边界外的每个单元都有8个相邻单元，如矩阵)。
回答 2
Stack Overflow用户
发布于 2012-08-06 21:52:33
您可以在此处使用flood fill，您的图形是G=(V,E)，其中V是格网，E = { (u,v) | there is a soldier in both u and v from the same unit }
基本上，当您将问题简化到这个图时，任何图发现算法都可以。从所需单元中的任何士兵调用该算法，如果发现算法准确发现了k节点，则可以判断该单元是否“连接”，其中k是该单元中的士兵数量。
Stack Overflow用户
发布于 2012-08-07 11:52:11
使用联合查找数据结构。测试每一对士兵。当两个士兵相邻时，它们的等价类被合并。在对所有这样的对进行测试之后，如果您最终只有一个等价类，那么您的单元就是连接的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11829465
复制相关文章
相似问题
腾讯云开发者
