# 种西瓜 3：题解

**本题解法设计与实现：Codex（GPT-6）。** 本解法基于已有的最小极大匹配三状态路径分解方法，采用逐格轮廓线转移，时间复杂度为 $O(nm\,3^w)$ ，其中 $w=\min(n,m)$ .

方法背景见 van Rooij 与 Bodlaender 的 [Exact Algorithms for Edge Domination](https://www.researchgate.net/publication/220992947_Exact_Algorithms_for_Edge_Domination)，其中给出了最小极大匹配的三状态路径分解动态规划。

## 匹配与终止条件

只在相邻的瓜藤与初始空地之间连边，障碍物以及同类格子之间没有边。结瓜关系是一组匹配；生长停止等价于每条边至少有一个已匹配端点。我们要求边数最少的极大匹配。

瓜藤数可以很大，但网格较窄。令 $V=nm$ 、$w=\min(n,m)$ .必要时转置网格，使列数为 $w$ ，然后按从上到下、每行从左到右的顺序扫描。

## 为什么只保存一条轮廓

处理格子 $(x,y)$ 之前，已经处理的格子中，仍可能与未来发生联系的只有：当前行左侧的格子，以及上一行中尚未被当前行替换的格子。用每列一个槽位保存它们，总共 $w$ 个槽位。

当前格子的上邻格在槽位 $y$ ；若 $y>0$ ，左邻格在槽位 $y-1$ .处理当前格子后，上邻格的所有邻边均已处理，它可以离开轮廓；当前格子占据槽位 $y$ .其他更早的格子无需保留。

![扫描当前格子时，上邻格离开轮廓，当前格子进入同一槽位](assets/frontier.svg)

浅色区域为已扫描部分，粗线框圈出轮廓中的格子。图中的 `u` 是上邻格，`v` 是左邻格，`c` 是当前格子。图左、图右分别表示处理 `c` 前后，格子类型仍由实际输入确定。

## 三种状态

每个轮廓顶点使用一个三进制位：

| 状态 | 含义 |
| --- | --- |
| $0$ | 决定最终不参与匹配。 |
| $1$ | 决定参与匹配，正在等待一个尚未处理的邻居作为搭档。 |
| $2$ | 已经匹配，不能再选择匹配边。 |

状态 $0$ 是最终承诺；状态 $1$ 必须在顶点离开轮廓之前兑现。这样，在处理一条边时，只要禁止两端都为 $0$ ，就保证该边最终至少有一个匹配端点。状态 $1$ 的端点即使当下尚未匹配，也不能被当作永久未匹配点。

记 $dp[M]$ 为当前轮廓编码 $M$ 对应的最少已选匹配边数。初始所有槽位都是无顶点的占位符，编码为零，只有 $dp[0]=0$ .是否真的存在边由输入字符和坐标决定，所以占位符与障碍格可以使用状态 $0$ ，不会产生假边。

## 每格的四种选择

设上邻格状态为 $a$ ，左邻格状态为 $b$ .只有瓜藤与空地相邻时才存在对应的边。

1. **当前格子最终不匹配。** 新状态设为 $0$ .上邻格将离开轮廓，故 $a\ne1$ ；每个与当前格子有边的上、左邻格都不能为 $0$ .
2. **当前格子等待未来搭档。** 新状态设为 $1$ .仍要求 $a\ne1$ .可进一步要求它的下方或右方确有合法邻边，否则这个等待永远无法兑现。
3. **与上邻格匹配。** 要求存在上邻边且 $a=1$ .当前格子成为 $2$ ，上邻格的承诺被兑现并离开轮廓，代价加一。
4. **与左邻格匹配。** 要求存在左邻边且 $b=1$ ，同时 $a\ne1$ .当前格子和左邻格都成为 $2$ ，代价加一。

第三、四种选择使当前格子已经匹配，因此它与另一个旧邻格之间的边自动满足终止条件。匹配过的端点不能再次使用；同一格只选择上述一种情况，因而不会同时向上、向左匹配。

用两个数组滚动更新。若 $P_y=3^y$ ，则第 $y$ 位可由 $\lfloor M/P_y\rfloor\bmod3$ 取出。覆盖该位、将左邻格从 $1$ 改成 $2$ 等操作都只需常数次整数运算。

全部格子处理完后，只接受没有状态 $1$ 的编码，并取最小代价。最后一行也必须完成所有等待，不能遗漏这个结束条件。

## 正确性

维护以下不变量：状态对应某个已扫描部分的合法部分匹配；已离开轮廓的顶点均兑现了自己的最终状态；已处理边不会连接两个最终不匹配的顶点；数组值是满足这些条件的最小已选边数。

四种选择完整划分了当前顶点在任意最终匹配中的角色：不匹配、搭档在未来、搭档在上方、搭档在左方。转移检查避免重复使用端点，离开轮廓时排除未兑现的等待，并检查所有新处理的边，因此保留不变量。反过来，任意合法最终匹配在每个格子都对应其中一种转移，不会被遗漏。

扫描结束且没有等待状态时，得到完整匹配；每条图边都至少有一个匹配端点，所以匹配极大。所有合法终止方案均被覆盖，取最小代价即得到最少结瓜数。

## 复杂度与实现

轮廓有 $w$ 位、每位三种状态，每格至多四个转移，因此时间复杂度为 $O(V3^w)$ .两个 DP 数组占 $O(3^w)$ 空间，保存输入和转置网格占 $O(V)$ ，总空间为 $O(V+3^w)$ .复杂度使用宽度参数 $w$ ，不把约束中的具体数值代入指数。

同类格子之间不连边，跨行时不存在“上一行末格到下一行首格”的边，网格外也没有边。程序根据实际坐标判断这些条件。没有瓜藤、没有空地或全部为障碍时，零代价状态自然保留。

## 验证与复现

直接枚举小棋盘上的所有匹配并检查极大性，覆盖全部 $2\times3$ 三状态棋盘及随机棋盘；中等实例与增量匹配及原《种西瓜》算法对照。更大实例检查转置、左右翻转、交换瓜藤与空地类型不改变答案，以及障碍行分隔的两个区域答案相加。

参考程序见 [std.cpp](std.cpp)，范围与种子见[生成计划](tests/plan.json)，性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。