检查所有迷宫墙是否连接的算法

Question

我正在构建一个迷宫游戏，并且正在寻找一种算法，如果它在迷宫中找到与迷宫中其余墙壁没有连接的墙或墙段，则该算法返回 true (即墙岛)。我用来测试用户生成的迷宫是否可解的迷宫求解算法是“右手法则”(我的算法类似于讨论的算法 here 和 here )，但它有可能如果一堵或多堵墙没有与其他所有墙相连，则会失败。

我的迷宫存储在 1 和 0 整数的二维数组中，代表每面墙的存在/不存在状态。

有谁知道计算迷宫(以上述格式保存)是否有任何墙壁与其余墙壁完全断开的最便宜的方法？

代码、伪代码或简单的英语条件大纲将不胜感激。如果有人正在寻找一种语言作为示例，我计划将其翻译成 javascript。

谢谢!

Answer 1

Flood-fill从某个起始墙开始的所有连接墙。您可以通过将墙壁设置为其他值(例如 2)或为此设置另一个 2D 数组来实现。

再次穿过迷宫。如果您发现在上述步骤中没有填充任何墙，我们知道它没有连接到其余部分。

但是通过仅将您已经访问过的单元格标记为已访问而不是重新访问已经访问过的单元格(再次使用另一个值或另一个数组，如多于)。如果这样做，墙壁是否连接并不重要。