algorithm - 我如何在迷宫中找到最佳的墙来拆除以产生最大的区域？

Question

我有一个由二维数组表示的迷宫。

bool[][] maze = ...

如果该位置有墙，则 maze[row][column] 为 True，如果该位置没有墙，则为 False。周边总是被墙包围。

目标是确定最大的房间，然后在迷宫中找到一个切点，如果您打破该点的墙，将创建新的最大房间。

是否有一种算法可以找到要打破的墙，从而创造出最大的房间？

是否应该将其建模为图表？

编辑:

我在随意乱扔房间这个词。一个房间是一个或多个连接在一起的非墙。

----------
|   |    |
|   |----|
|   |    |
----------

maze = { {True, True, True, True, True},
         {True, False, True, False, True},
         {True, False, True, True, True},
         {True, False, True, False, True},
         {True, True, True, True, True} }

这张图包含三个房间。它们的面积是 3、1 和 1。最佳切割点是 (1,2) 或 (3, 2)。这些中的任何一个都会生成一个面积为 5 的房间。

Answer 1

Union-find在这里似乎是一个合适的算法。

只需遍历网格并将每个非墙单元与其非墙邻居合并。

然后遍历集合以找到最大的一个(这是最大的房间)。

然后再次遍历网格，对于每一面墙，检查将墙的不同边合并在一起的大小(只记录大小，不要实际执行合并)。最大的记录联合将指示墙被打破以创建最大的房间。

对于所有远程实际大小的网格，使用已知优化联合查找的运行时间为 O(rowCount*columnCount)(线性)。