0

我有一个“块”网格(以 2D 数组的形式,可以是 5*5、17*17 或其他),我可以随意添加或删除块,除了中心应该始终保留的块那里。

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

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

我正在寻找一个快速的解决方案来检查我的所有块是否都与中心有连接,这是最简单的(就编码而言,我可以接受有一个非最佳解决方案,因为这应该在非常小的情况下执行数据,而不是经常)。我想到的第一件事是将其实现为路径搜索,但这似乎有点过头了。

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

4

1 回答 1

1

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

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

于 2013-07-03T12:20:24.837 回答