algorithm - 在网格中查找孤立的 block 组

Question

我有一个“ block ”网格(以二维数组的形式，可以是 5*5、17*17 或其他)，我可以在其中随意添加或删除 block ，except对于位于中心的那个应该始终保持在那里。

如果他们有本地邻居，我可以放置 block :在他们的右/左/上/下(至少其中一个)。

通过删除一些 block ，它可能会使其他 block 与中心 block 没有“连接”隔离，我想避免这种情况。

我正在寻找一种快速解决方案来检查我的所有 block 是否都连接到中心，尽可能简单(就编码而言，我可以接受非最佳解决方案，因为这应该是在执行在非常小的数据上而且不那么频繁)。我想到的第一件事是将其实现为路径搜索，但这似乎有点过分了。

我正在使用 C++，但这应该没有任何区别。

Answer 1

您需要使用 DFS/BFS 找到连接的组件。构造初始图，并在添加新 block 时添加新边，或者在删除 block 时删除边。删除 block 时，暂时删除图中的那些边，检查它是否导致两个图断开。这个很简单，再次进行DFS。如果没有断开，则可以删除该 block 。

DFS 只需大约 8 行代码即可实现，对于小型数据集来说这很优雅。