迷宫游戏

在这个迷宫游戏中，你需要实现一个算法来帮助角色从起点到达终点。

游戏规则

• 迷宫是一个二维网格，由墙壁和通路组成
• 角色只能在通路中移动，不能穿过墙壁
• 目标是从起始位置（绿色方块）到达终点（红色方块）
• 你可以使用键盘方向键或点击屏幕按钮来手动控制角色移动

你的任务

实现一个 solveMaze 函数，通过操作 gameController 来自动解决迷宫问题。

输入

gameController 是一个对象，提供了以下方法：

• isVisited(i, j): 判断坐标 (i, j) 处的单元格是否已访问

  • i 是行索引，j 是列索引，左上角为 (0, 0)
  • 返回 true 表示已访问，false 表示未访问
  • 如果是墙壁或边界会抛出错误

• isEmpty(i, j): 判断坐标 (i, j) 处的单元格是否为空（未访问的通路）

  • 返回 true 表示是空的通路，false 表示已访问或是墙壁

• isBlock(i, j): 判断坐标 (i, j) 处是否为墙壁或边界

  • 返回 true 表示是墙壁或边界，false 表示是通路

• setVisited(i, j, visited): 设置坐标 (i, j) 处的访问状态

  • visited 为 true 标记为已访问，false 标记为未访问
  • 注意：墙壁位置不能设置，操作无效位置会抛出错误

• getPosition(): 获取玩家当前位置

  • 返回 {i: number, j: number}

• getTargetPosition(): 获取终点位置

  • 返回 {i: number, j: number}

• setPosition(i, j): 移动玩家到指定位置

  • 只能移动到相邻的格子（曼哈顿距离为1）
  • 不能跳跃移动，无效操作会抛出错误

使用示例

// 获取当前玩家位置
const currentPos = gameController.getPosition();
console.log("当前位置:", currentPos);

// 获取终点位置
const targetPos = gameController.getTargetPosition();
console.log("终点位置:", targetPos);

// 检查右边的单元格状态 (当前列+1)
if (gameController.isEmpty(currentPos.i, currentPos.j + 1)) {
  // 移动到右边
  gameController.setPosition(currentPos.i, currentPos.j + 1);
  // 标记为已访问
  gameController.setVisited(currentPos.i, currentPos.j + 1, true);
}

算法提示

你可以使用以下算法来解决迷宫问题：

• 深度优先搜索 (DFS): 沿着一条路径深入探索，直到无路可走再回溯
• 广度优先搜索 (BFS): 逐层探索，保证找到最短路径
• A*算法: 使用启发式函数的最优路径搜索算法

注意事项

• 起始位置通常是绿色方块，终点是红色方块
• 你可以通过 setState 方法来标记已访问的路径，方便可视化
• 移动时请确保目标位置是有效的（非墙壁且相邻）

祝你好运！