迷宫生成器

在这个挑战中，你需要实现一个迷宫生成算法，创建一个既有挑战性又有解的随机迷宫。

迷宫生成要求

• 生成的迷宫必须是连通的（从任意一点都能到达任意另一点）
• 迷宫应该具有足够的复杂性和随机性
• 避免生成过于简单或过于复杂的迷宫
• 确保生成的迷宫有唯一解（或接近唯一解）

经典算法推荐

1. 深度优先搜索 (DFS) 算法

1. 从一个随机起点开始，标记为已访问
2. 随机选择一个未访问的相邻单元格
3. 移除两个单元格之间的墙壁，移动到新单元格
4. 重复步骤2-3，直到无路可走时回溯
5. 继续直到所有单元格都被访问

2. 随机 Prim 算法

1. 选择一个随机起点，加入到迷宫中
2. 将起点的所有墙壁加入到墙壁列表
3. 随机选择一个墙壁，如果它连接的两个单元格中只有一个在迷宫中，则移除这个墙壁
4. 将新单元格加入迷宫，并将其墙壁加入列表
5. 重复直到墙壁列表为空

3. 递归分割算法

1. 从整个网格开始
2. 随机选择一个方向（水平或垂直）进行分割
3. 在分割线上随机选择一个点作为通道
4. 递归地对每个子区域重复此过程

游戏控制器接口

gameController 提供以下方法来操作迷宫网格：

• getGrid(): 获取当前网格状态

  • 返回二维数组，true 表示墙壁，false 表示通路
  • 可以通过 grid.length 获取高度，grid[0].length 获取宽度

• setEmpty(row, col): 将指定位置设置为通路

  • row: 行索引 (0-based)
  • col: 列索引 (0-based)

• setBlock(row, col): 将指定位置设置为墙壁

  • row: 行索引 (0-based)
  • col: 列索引 (0-based)

重要说明

• 起点: 位于左上角 (0, 0)，显示为绿色格子
• 终点: 位于右下角 (width-1, height-1)，显示为红色格子
• 生成的迷宫必须确保从起点到终点有可通行的路径

祝你生成出精彩的迷宫！