死角剪枝是提升求解速度最有效的手段。推箱子里有个概念叫永久死角:某个地板格,横竖两个方向都被墙或死角堵死,箱子推进去就永远出不来。不是目标格的箱子进去就无解。

    搜索前先算一遍所有格子的死角属性。一个格子是死角,当且仅当它不是目标格,且横竖都推不动箱子——要么尽头是墙,要么尽头的格子也是死角。从墙边往里扩散判定,比暴力枚举快。

    function computeDeadCells() {
      // 从墙和死角落开始标记
    }
    

    搜索展开时,箱子被推到死角格,直接剪掉这条分支。这一步省掉的状态数非常可观,复杂关卡剪枝前后搜索量能差几个数量级。

    有人问临时死角要不要算,就是箱子进去能出来但要绕路的那种。只剪永久死角够用,临时死角判定成本高,收益不明显,我的做法是不剪。