本题的难点是, 移动的箱子造成了地图的不断变化, 箱子所在的点会成为障碍, 可能导致一些本能走到的位置不再相连...这不是割点吗?! 在无向连通图中, 对于割点的定义是: 若删去该点及其连边, 图不再连通. 所以我们可以试着强行用Tarjan跑出地图上所有割点的坐标, 顺便取得每个点所隶属的点双连通分量编号 ( 所以, 割点应该隶属于多个点双 ), 接下来我们讨论如何快速判断能否从某个方向推动箱子, 假设现有状态"A−box−B" ( 具体来说, 设有两个位置A, B与箱子box相邻 ): 首先由题意, 在不考虑box的阻挡时, A与B应当由一条经过box位置的路径相连. 若考虑box的阻挡, A与B不再相通, 则由论述1. A, B之间有且仅有一条经过box位置的路径相连. 那么由割点的定义, box的位置是割点, A, B一定不属于同一个点双. 于是得出结论: A在box的阻挡下能到达B⟺A, B隶属于同一个点双. 剩下的一切好说. 我就调了俩小时. 所以我们再捋一捋代码: Tarjan, 求出每个点隶属的 ( 一个或多个 ) 点双编号. BFS/DFS, 预处理, 尝试让人物靠近箱子的四个方向, 并保存能到达的方向. BFS, 利用上述判别方法, 标记每个箱子能到达的位置. emmm再好心地说一下细节问题吧: 有的小朋友为了方便判断有无相同的点双编号, 会选择使用set等STL储存每个点所隶属的点双编号, T掉一大半, 开O2就能A。 关于最终的BFS如何储存状态, 定义Vis[i][j][k]表示箱子在(i,j), 人物在箱子的k方向即可. 好了, 上代码吧