我有一个由二维数组表示的迷宫。
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的房间。