BFS 不加去重会爆炸。一个局面可以从不同路径到达,不去重的话同一个状态会被反复展开,状态数指数级增长,几关下来浏览器就卡死了。
去重的思路是给每个状态算一个唯一 key。箱子集合是无序的,排序后拼成字符串,玩家坐标也拼进去。这样不管箱子怎么排列,同样的布局会得到同样的 key,搜过就不再入队。
function key(state) {
const boxes = [...state.boxes].sort().join(',');
return state.player.r + ',' + state.player.c + '|' + boxes;
}
if (visited.has(k)) continue;
visited.add(k);
queue.push(next);
visited 用 Set 存 key 字符串。有人想用二维数组当查重表,理论上更快,但状态空间太大,数组开不下。字符串 key 够用,内存是主要瓶颈,不是查找速度。
注意箱子排序要稳定。如果用 Set 存箱子,迭代顺序不固定,每次排序结果可能不同,同一个布局算出不同 key。先用数组存再排序,避免这个问题。
