题解：P14474 拼积木

解法如下。首先，我们把状态理解为一个网格图（同时是二分图），每个积木对应一条边。则一个状态是一个匹配边集。求初始状态和最终状态的对称差图，由于匹配中每个点度数 $\le 1$，对称差图每个点度数一定 $\le 2$。所以图上只可能有四种联通块：

首先，我们可以通过一次操作让对称差图上一条交替路长度减 $2$（对于“奇交替路（最终状态边多）”这种情况需要去操作目标图倒着移动。移动可逆，所以先用栈记录下来这种移动，实际操作时最后倒着移回去就行。）。所以先通过 $\le n^2/2$ 次操作消除所有的偶交替路并将所有奇交替路长度减到 $1$ 条边。（$1$ 条边的交替路相当于扣掉/加上一整块积木）

然后我们把对称差图上剩下的长为 $1$ 的奇交替路（其实就是 $1\times 2$ 的空格位置）随意配对。这样，我们需要交换一块 $1\times 2$ 的积木和一个 $1\times 2$ 的空格的位置。我们可以按任意一个曼哈顿距离最短的路线移动，每次交换一块积木和相邻位置的一个 $1\times 2$ 空格，每移一格均摊最多操作 $2$ 次。（注意有可能有跨过中间很多个空格的情况，需要特殊处理之后第一个碰到的积木移动）总移动次数 $\le S/2 \times 2 \times 2n$（$S$ 为总空格数）。问题输入限制总空格数 $\le n/2$ 之后是 $\le n^2$。

然后就只剩交替环了。这部分套用原来的题（P5372 [SNOI2019] 积木）的做法即可。记得每个积木连通块分别处理。这部分 $\le 2n^2$

总共操作次数 $\le 3.5 n^2$