如何在迷宫中找到最佳的墙壁，以生成最大的区域？

Question

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

bool[][] maze = ...

其中maze[row][column]为True表示该位置有墙，为False表示该位置没有墙。迷宫的周围总是被墙包围。

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

是否存在一种算法可以找到要打破的墙壁，以创建最大的房间?

这应该建模为一个图吗？

编辑:

我随意地使用了单词“room（房间）”。一个房间由一个或多个非墙体连接在一起。

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

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的房间。

- sdasdadas

---

你在使用单词“room”时有两个不同的定义：一次用于描述二维数组中的一个元素，另一次用于描述当你拆除一堵墙时所创建的区域。请更好地定义你所指的第二个含义。 - John

我认为我们需要比你目前提供的更多关于数据结构的信息。也许是迷宫的图形（不一定是图表）。 - Scott Solmer

@John 你是对的-我已经尽力更清楚地解释了。 - sdasdadas

任何一个都可以生成一个面积为5的房间。也许它可以用流问题来表示 :/ - Fractaliste

@Fractaliste 谢谢你修复了。 - sdasdadas

Answer 1

并查集 算法似乎是这里的一个合适的算法。

只需遍历整个网格，将每个非墙单元格与其相邻的非墙单元格进行合并。

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

然后再次遍历网格，并对每堵墙检查将不同侧的墙壁合并在一起的大小（只记录大小，而不实际执行合并）。最大记录的联合将指示拆除哪堵墙以创建最大的房间。

使用已知优化的并查集的运行时间对于所有远程实用的网格大小都为 O(rowCount*columnCount)（线性）。

- Bernhard Barker

Answer 2

我能立即想到的方法是暴力破解，这种情况下并不太低效，因为它只需要多项式时间。只需尝试删除每个部分，看哪一个可以创建最大的空间。

以下是使用该方法的伪代码。

int[] removeBestWall(maze) {
  int maxSize = 0;
  int[] bestWall = [0, 0]
  for(int i = 1; i < maze.width - 1; i++) {
    for(int j = 1; j < maze.height - 1; j++) {
      int size = getRoomSize(maze, i, j);
      if(size > maxSize) {
        maxSize = size;
        bestWall = [i, j];
      }
    }
  }
  return bestWall;
}

int getRoomSize(maze, i, j) {
  if(maze[i][j] == True) return 0;
  int size = 1;
  bool[][] newMaze = make;
  newMaze[i][j] = True;
  return size + 
   getRoomSize(newMaze, i, j + 1) +
   getRoomSize(newMaze, i, j - 1) +
   getRoomSize(newMaze, i + 1, j) +
   getRoomSize(newMaze, i - 1, j);
}

- Peter Olson

Answer 3

我同意你展示的数据结构是含糊不清的。你需要两个数组：一个用于水平墙壁，一个用于垂直墙壁。另一种布局方式是作为单元格结构的数组，每个结构体保存其右侧和底部墙壁的布尔值。

由于您始终在寻找两个房间之间的一堵墙，这相当于查找总面积最大的两个相邻房间。首先要识别房间并制作列表。这是通过深度或广度优先搜索开放方块的森林来完成的。森林的每个连通分量都是一个房间。该区域是组件中方块的数量。

接下来，您需要知道哪些房间共享每堵墙。这只是通过循环遍历所有内部墙壁并找到相邻房间来完成的。然后，您将拥有每个墙壁和两个相关房间的列表。

最后，遍历此列表并选择相邻房间总面积最大的墙壁。

有多种方法可以使此计算快速进行，但除非暴力法的基准测试过慢，否则这是过早的优化。我敢肯定，在500x500迷宫上，这将在不到一秒的时间内运行良好。

- Gene