种西瓜 3：题解¶
本题解法设计与实现：Codex（GPT-6）。 本解法基于已有的最小极大匹配三状态路径分解方法，采用逐格轮廓线转移，时间复杂度为 \(O(nm\,3^w)\) ，其中 \(w=\min(n,m)\) .
方法背景见 van Rooij 与 Bodlaender 的 Exact Algorithms for Edge Domination，其中给出了最小极大匹配的三状态路径分解动态规划。
匹配与终止条件¶
只在相邻的瓜藤与初始空地之间连边，障碍物以及同类格子之间没有边。结瓜关系是一组匹配；生长停止等价于每条边至少有一个已匹配端点。我们要求边数最少的极大匹配。
瓜藤数可以很大，但网格较窄。令 \(V=nm\) 、\(w=\min(n,m)\) .必要时转置网格，使列数为 \(w\) ，然后按从上到下、每行从左到右的顺序扫描。
为什么只保存一条轮廓¶
处理格子 \((x,y)\) 之前，已经处理的格子中，仍可能与未来发生联系的只有：当前行左侧的格子，以及上一行中尚未被当前行替换的格子。用每列一个槽位保存它们，总共 \(w\) 个槽位。
当前格子的上邻格在槽位 \(y\) ；若 \(y>0\) ，左邻格在槽位 \(y-1\) .处理当前格子后，上邻格的所有邻边均已处理，它可以离开轮廓；当前格子占据槽位 \(y\) .其他更早的格子无需保留。
浅色区域为已扫描部分，粗线框圈出轮廓中的格子。图中的 u 是上邻格，v 是左邻格，c 是当前格子。图左、图右分别表示处理 c 前后，格子类型仍由实际输入确定。
三种状态¶
每个轮廓顶点使用一个三进制位：
| 状态 | 含义 |
|---|---|
| \(0\) | 决定最终不参与匹配。 |
| \(1\) | 决定参与匹配，正在等待一个尚未处理的邻居作为搭档。 |
| \(2\) | 已经匹配，不能再选择匹配边。 |
状态 \(0\) 是最终承诺；状态 \(1\) 必须在顶点离开轮廓之前兑现。这样，在处理一条边时，只要禁止两端都为 \(0\) ，就保证该边最终至少有一个匹配端点。状态 \(1\) 的端点即使当下尚未匹配，也不能被当作永久未匹配点。
记 \(dp[M]\) 为当前轮廓编码 \(M\) 对应的最少已选匹配边数。初始所有槽位都是无顶点的占位符，编码为零，只有 \(dp[0]=0\) .是否真的存在边由输入字符和坐标决定，所以占位符与障碍格可以使用状态 \(0\) ，不会产生假边。
每格的四种选择¶
设上邻格状态为 \(a\) ，左邻格状态为 \(b\) .只有瓜藤与空地相邻时才存在对应的边。
- 当前格子最终不匹配。 新状态设为 \(0\) .上邻格将离开轮廓，故 \(a\ne1\) ；每个与当前格子有边的上、左邻格都不能为 \(0\) .
- 当前格子等待未来搭档。 新状态设为 \(1\) .仍要求 \(a\ne1\) .可进一步要求它的下方或右方确有合法邻边，否则这个等待永远无法兑现。
- 与上邻格匹配。 要求存在上邻边且 \(a=1\) .当前格子成为 \(2\) ，上邻格的承诺被兑现并离开轮廓，代价加一。
- 与左邻格匹配。 要求存在左邻边且 \(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\) 三状态棋盘及随机棋盘；中等实例与增量匹配及原《种西瓜》算法对照。更大实例检查转置、左右翻转、交换瓜藤与空地类型不改变答案，以及障碍行分隔的两个区域答案相加。