推箱子

推箱子(Sokoban)是一个经典的益智游戏，你需要控制仓库管理员推动箱子到指定位置。

游戏规则

• 玩家控制一个仓库管理员，可以上下左右移动
• 管理员可以推动箱子，但不能拉动箱子
• 目标是将所有箱子推到目标位置上
• 管理员不能推动多个箱子，也不能穿越墙壁或箱子
• 箱子不能推出边界或推到墙壁上

你的任务

实现一个 solvePushBox 函数，通过操作 gameController 来自动解决推箱子问题。

输入

gameController 提供以下方法：

• getBoard(): 获取当前游戏板状态

  • 返回二维数组，包含不同类型的格子：
  • 0: 空地
  • 1: 墙壁
  • 2: 目标位置
  • 3: 箱子
  • 4: 玩家
  • 5: 箱子在目标位置上
  • 6: 玩家在目标位置上

• move(direction): 移动玩家

  • direction: 'up', 'down', 'left', 'right'
  • 如果移动导致推动箱子，会自动处理箱子移动
  • 无效移动会被忽略

算法提示

• 广度优先搜索(BFS): 寻找最短步数解
• A*算法: 使用启发式函数优化搜索
• 状态压缩: 用字符串或哈希表记录访问过的状态
• 回溯算法: 深度优先搜索所有可能的移动序列

注意事项

• 需要避免重复访问相同的游戏状态
• 可以使用曼哈顿距离作为启发式函数
• 考虑死锁检测（箱子被推到无法移动的位置）

祝你好运！