BFS 求解器是推箱子的大脑。核心思路把状态当成节点:玩家站在哪个格子、箱子分布在哪些位置,这两个信息加起来就是一个完整的局面。从一个状态出发,朝四个方向移动展开,每个新状态都是一个邻居节点,BFS 一层一层往外扩,直到碰到胜利状态。
状态怎么表示?箱子用坐标集合,玩家用一个行列号。每次移动判断玩家能不能走到目标格,如果能且目标格是箱子,再判断箱子能不能被推走。推得动就生成新状态,推不动就跳过。
const queue = [{player, boxes}];
while (queue.length) {
const cur = queue.shift();
if (isSolved(cur.boxes)) return cur;
for (const [dr, dc] of DIRS) {
// 展开四个方向,生成新状态
}
}
BFS 能保证找到最短路径,因为队列是先进先出,第 N 层状态一定在第 N+1 层之前处理。这个性质对求理论最少步数很重要,星级阈值就靠它。代价是状态数增长快,去重和剪枝必须跟上,否则搜索会炸。
