题解：SP208 STORE - Store-keeper

我们关心的是箱子的移动次数，而不是人的。所以箱子的位置相同，人在任何位置都是等价的……吗？

并不是，箱子会挡人。箱子可能让本来连通的部分变得不连通，但是在同一个连通块（考虑了箱子）之内的确实是等价的。

显然，我们只需要考虑人在箱子的相邻上/下/左/右四个方位的情况。其余情况要么可以转化为这四种情况，要么不可达。

我们设 $f_{i,j,k}$ 为箱子坐标为 $(i,j)$ 而人在箱子的 $k$ 方位，其中 $k=1,2,3,4$ 分别表示上、下、左、右。那么考虑一次移动：

后者是很好处理的，只需要 $\Theta(1)$ 次判断。而前者则需要思考。

去掉一个点后，两点的连通性。你想到了什么？没错，割点！

根据定义，同一个点双连通分量中，去掉任意一个点后还是连通的。如果不在一个点双连通分量呢？

考虑到它们不在同一个点双连通分量，故它们之间至多有一条节点互不相交的路径（除了两个端点相同）。而它们之间的一条路径一条就是连接到去掉的点，又连接到另一个点的。除去端点就只有一个点：删除的点。所以两者之间所有路径都经过这个点，删掉之后必然不连通！

所以我们就得到了结论：连通当且仅当属于同一个点双连通分量！就可以进行第一个转移了。

最后考虑到转移代价为 $0$ 或 $1$，使用 01-bfs 解决。考虑时间复杂度？

所以总时间复杂度达到了最优的 $\Theta(nm)$（输入数据都需要这么多时间）！

另：此题出处是 POI 1999，也是 BZOJ 2574，可以在此提交（截至本文编写日期 $2025/7/29$，黑暗爆炸是爆炸的状态）。