在 NxM 板上制造障碍
Generating obstacles on NxM board
我有 NxM 板。我想给它添加 K 个障碍，但在某种程度上，仍然可以从每个空 space 到每个其他空 space。我希望它看起来像这样
蓝色方块是障碍物。
换句话说，我有一个图形网格，我想从中随机删除 K 个顶点而不断开它。
我知道我可以通过从一个节点执行 dfs 并删除最远的顶点来做到这一点，但它不会真的是随机的，它看起来不太好，这不是我想要的。
有没有算法可以做我想做的事，或者有没有人有一些想法可以测试？
编辑：典型的迷宫生成算法不适用于我的情况，因为据我了解，它们通过从图中删除边来工作，在这里我需要删除整个顶点
您可以使用不相交的集合数据结构来执行此操作：https://en.wikipedia.org/wiki/Disjoint-set_data_structure
- 每个顶点都分配给一个集合，该集合标识"boundary"它是
的一部分
- 最初，外边界上的顶点都在同一个集合中，每个内部顶点都在自己的集合中。
- 随机选择一个"valid"方格并填充它。相应地合并其4个角的边界集。
- 重复直到选择了 K 个方块
一个正方形是 "invalid" 如果填充它会创建一个边界循环：
- 任何有 3 个填充邻居的未填充方块都是有效的。否则...
- 对于每个未填充的邻居，如果其相邻角在同一边界内，则填充正方形将创建一个循环，因此它是无效的。
- 如果任意一对对角在同一边界内，但其他角都不在同一边界内，则填充正方形会形成环，因此无效。
为了实现高效，请以伪随机顺序随机尝试所有方块。由于填充正方形可能会使之前无效的正方形变为有效，但是，每当您填充正方形时，请将其之前排除的邻居重新添加到可能性池中。
我有 NxM 板。我想给它添加 K 个障碍，但在某种程度上，仍然可以从每个空 space 到每个其他空 space。我希望它看起来像这样
蓝色方块是障碍物。
换句话说，我有一个图形网格，我想从中随机删除 K 个顶点而不断开它。
我知道我可以通过从一个节点执行 dfs 并删除最远的顶点来做到这一点，但它不会真的是随机的，它看起来不太好，这不是我想要的。
有没有算法可以做我想做的事，或者有没有人有一些想法可以测试？
编辑：典型的迷宫生成算法不适用于我的情况，因为据我了解，它们通过从图中删除边来工作，在这里我需要删除整个顶点
您可以使用不相交的集合数据结构来执行此操作：https://en.wikipedia.org/wiki/Disjoint-set_data_structure
- 每个顶点都分配给一个集合，该集合标识"boundary"它是 的一部分
- 最初，外边界上的顶点都在同一个集合中，每个内部顶点都在自己的集合中。
- 随机选择一个"valid"方格并填充它。相应地合并其4个角的边界集。
- 重复直到选择了 K 个方块
一个正方形是 "invalid" 如果填充它会创建一个边界循环：
- 任何有 3 个填充邻居的未填充方块都是有效的。否则...
- 对于每个未填充的邻居，如果其相邻角在同一边界内，则填充正方形将创建一个循环，因此它是无效的。
- 如果任意一对对角在同一边界内，但其他角都不在同一边界内，则填充正方形会形成环，因此无效。
为了实现高效，请以伪随机顺序随机尝试所有方块。由于填充正方形可能会使之前无效的正方形变为有效，但是，每当您填充正方形时，请将其之前排除的邻居重新添加到可能性池中。