题解:CF1949J Amanda the Amoeba
从一个状态变到另一个状态,考虑找中间态。这个中间态一般具有极端、有序的特征。
我们希望变形虫变到一个极端的状态,首先就想到可以堆到一个角上。因为不知道怎么堆,我们考虑把每个格子编一个号,最后得到字典序最小的点集。
怎么编号以及移动使得最后的结果唯一且一定可行呢?考虑爬一棵网格图的生成树出来,然后如果可以拿一个叶子来放到某个节点的父亲就先放,把它抵到最上面,再调整到最小状态。
具体实现上,只需每次找当前覆盖最大编号,把它变成最小可达编号即可。要判掉割点。