J. 变形虫阿曼达 详细题解

题目核心理解

变形虫在方格网格中移动，每一步必须先移除一个叶子像素（保持连通），再在另一个空闲位置添加一个像素，全程身体保持连通。 给定初始形态和目标形态（大小相同、均连通、障碍固定），要求输出合法移动序列，或判断无解。

---

核心思路

1. 关键性质

• 存在解的充要条件：存在一条连接初始区域与目标区域的路径，中间只经过空地。
• 变形虫的移动等价于：把初始形状“拆成树”，再沿着路径搬到目标形状“拼成树”。
• 删点只能删叶子，加点只能连到当前身体，保证全程连通。

2. 构造规则

1. 找点 $A$（初始身体）、点 $B$（目标身体），以及路径 $Q_{AB}$（全为空地）。
2. 用 BFS/DFS 构造初始树 $T_A$、目标树 $T_B$。
3. 自底向上删除 $T_A$ 叶子，依次填充路径 $Q_{AB}$。
4. 自顶向下加入 $T_B$，先加根 $B$，再依次加子节点。
5. 最后移除路径点并补到 $T_B$ 底部，得到目标形状。

3. 冲突处理

• 若某点同时在 $T_A$ 和 $T_B$：先正常删除，后面再加回来。
• 若某点还在身体里就需要加入：跳过不删，直接保留，保证连通。

---

算法流程

1. 读取网格、初始形态、目标形态与障碍。
2. 检查初始与目标之间是否存在可达空地路径，不存在则输出 NO。
3. 对初始形态做 BFS/DFS 生成树 $T_A$，对目标形态生成树 $T_B$。
4. 后序遍历 $T_A$ 删叶子，将删除的点依次移动到 $Q_{AB}$ 与 $T_B$。
5. 输出所有移动操作，步数不超过 $r\cdot c \le 2500$，满足题目限制。

---

公式与复杂度分析

可达性判定：

$$\text{reachable}(S, T) \iff \text{存在路径 } S \to Q_{AB} \to T $$

单步操作：

$$\text{remove}(leaf) \implies \text{add}(neighbour\ of\ body) $$

复杂度

• 路径查找：$O(rc)$
• 树构造：$O(rc)$
• 移动构造：$O(rc)$
• 总时间复杂度：$O(rc)$

可轻松处理 $r,c\le 50$，总像素 $\le 2500$，步数远小于 $10000$ 限制。