algorithm - 在 NxM 板上产生障碍

Question

我有 NxM 板。我想给它添加 K 个障碍物，但在某种程度上，仍然可以从每个空的空间到每个其他的空空间。我希望它看起来像这样



其中蓝色方块是障碍物。

换句话说，我有一个图形网格，我想从中随机删除 K 个顶点而不断开它。

我知道我可以通过从一个节点执行 dfs 并删除最远的顶点来做到这一点，但它不会真的是随机的，它看起来不太好，也不是我想要的。

是否有可以做我想做的事情的算法，或者有没有人有一些想法可以测试？

编辑:典型的迷宫生成算法不适用于我的情况，因为据我所知，它们通过从图中删除边来工作，在这里我需要删除整个顶点

Answer 1

您可以使用不相交的集合数据结构来做到这一点:https://en.wikipedia.org/wiki/Disjoint-set_data_structure

每个顶点都分配给一个集合，该集合标识它是

的一部分的“边界”。

最初，外边界上的顶点都在同一个集合中，每个内部顶点都在自己的集合中。

随机选择一个“有效”的正方形并填充它。相应地合并其 4 个角中每个角的边界集。

重复直到选择了 K 个方格

一个正方形是“无效的”，如果填充它会创建一个边界循环:

任何有 3 个填充邻居的未填充方块都是有效的。否则...

对于每个未填充的邻居，如果它的相邻角在同一边界内，那么填充正方形将创建一个循环，因此它是无效的。

如果任一对角在同一边界内，但其他角均不在同一边界内，则填充正方形将形成循环，因此无效。

为了有效实现，请以伪随机顺序随机尝试所有方块。由于填充一个正方形可能会使以前无效的正方形有效，但是，每当您填充一个正方形时，请将其先前排除的邻居重新添加到可能性池中。