在网格上填充瓷砖，以便可以访问所有未填充的瓷砖

Question

有人能告诉我一种解决以下问题的算法吗：

假设我有一个10*10的瓷砖网格。每个磁贴可以是“满”（玩家不能在上面行走）或“空”（玩家可以在上面行走）。我想遍历并随机填充瓷砖（以创建更有趣的地图），但是我需要所有“空”瓷砖才能访问。下面是一个快速图形：

我们从以下方面着手：

 _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|

然后仔细检查并填充一些瓷砖：

 _ _ _ _ _ _ _ _ _ _
|#|_|_|#|_|#|_|_|_|_|
|_|_|#|_|_|_|_|_|#|_|
|_|_|#|_|_|#|#|_|#|_|
|_|_|_|_|#|#|#|_|_|#|
|_|#|_|_|_|_|_|_|_|_|
|_|_|_|#|_|#|_|#|_|_|
|#|#|_|_|_|_|#|_|_|#|
|_|_|_|_|#|_|#|_|_|_|
|_|_|#|_|_|_|_|#|_|_|

并删除所有额外的行（仅用于显示）：

 _ _ _ _ _ _ _ _ _ _
|#     #   #        |
|    #           #  |
|    #     # #   #  |
|        # # #     #|
|  #                |
|      #   #   #    |
|# #         #     #|
|        #   #      |
|_ _ # _ _ _ _ # _ _|

如您所见，我们现在剩下的地图更有趣，并且可以随机生成（基于我们如何决定何时“填充”磁贴）。但是，使用简单的随机性可能会导致这样的情况：

 _ _ _ _ _ _ _ _ _ _
|#     #   #       #|
|    #     #     #  |
|    #     #     #  |
|      # #         #|
|  #                |
|      # # #     #  |
|#     #     #     #|
|      # # # #      |
|_ _ # _ _ _ _ # _ _|

在这里，有很多空间与地图的其余部分隔开。如果玩家从这些“房间”之外开始，就不可能进去。如果他们从其中一个“房间”开始，他们就无法出去。我知道我可以用洪水填充或类似的东西来测试这个，但这意味着我必须生成新地图，直到其中一个随机符合这些标准。我想的是一个新的“填充”图块规则集。现在我只是在每个图块中走动，并检查随机数是否高于阈值。如果是填写，如果不是，请转到下一个图块。然而，这意味着网格中的每个磁贴都与另一个磁贴完全无关。我一直在思考许多可能有帮助的规则集，尽管我可以理解其中的大部分。如果有人有任何建议，请告诉我

Answer 1

您可以遵循以下方法：

我们可以用你的图块创建一个图，图块是图的节点，如果两个图块都是填充的且相邻的，则定义边（如果你的玩家可以对角移动，则对角线是可选的）。若要支撑边，请将栅格设为12*12并填充所有边。在此图中，当且仅当图中存在循环时，才会隔离平铺，因此您可以随机填充平铺值，并检查新图是否仍然是树，否则重新填充并进入下一个尾部。可以使用DFS检查图形是否为树。

Answer 2

预防性方法

在这种方法中，您不允许形成封闭空间。

其中一种方法是使用联合查找或不相交集数据结构。

一个以封闭空间结束，如果

• 不接触边界：形成循环
• 带触摸边框：两个不相邻（水平或垂直）的全瓷砖，通过全瓷砖的某个路径连接，也与边框连接

因此，当您填满此网格时，对于每个被选为完整磁贴的磁贴，使用联合查找有效地检查上述两种情况。

纠正方法

在这种方法中，您使用一些完整的磁贴随机填充网格。这种方法可能会形成封闭的空间。现在使用完整磁贴的联合查找数据结构或空磁贴的泛滥填充来检测空间是否关闭。如果空间已关闭，请通过清空一些完整的磁贴来纠正它。要清空哪些完整的磁贴？可能有多种方法。其中一种可能是清空与封闭空间相关的完整磁贴，这些磁贴触及边界或形成循环。同样，对于这种联合查找或任何与图连接相关的算法，如BFS、DFS等。可以使用。

如果我有更多的想法，我会让你知道的。希望以上帮助。