题目理解与关键观察

1. 游戏局面特殊性

题目给出了一个关键条件：当前局面中，每个 $1\times 1$ 的格子都恰好有 0 或 2 条未连线的边。

这个条件的深层含义是：

• 所有格子被分成了若干连通分量
• 每个连通分量是一个环状结构（可能包含多个格子）
• 分量内部的格子通过未画的边连接在一起
• 分量之间完全独立（没有未画的边连接不同分量）

2. 连通分量的性质

在一个连通分量中：

• 所有未画的边构成了一个简单环或多个嵌套的环
• 当玩家在分量中画一条边时，有两种情况：
  1. 不得分：如果这条边不会立即完成任何格子
  2. 得分并继续行动：如果这条边完成了一个或多个格子

3. 游戏进程分析

对于单个连通分量，游戏进程是这样的：

• 玩家轮流在分量中画边
• 当画某条边完成一个格子时，该玩家得分并继续行动
• 当画某条边完成两个格子时（在角上），该玩家得2分并继续行动
• 游戏在分量中所有边都被画完后结束

核心解法思路

1. 问题分解

由于连通分量之间完全独立，整个游戏可以分解为多个独立的子游戏。根据组合博弈论的Sprague-Grundy定理思想，我们可以：

1. 分别计算每个连通分量在最优策略下的得分（$S_A - S_T$）
2. 将所有分量的得分相加，得到最终结果

2. 单个连通分量的分析

对于包含 $k$ 个格子的连通分量：

• 总共有 $k+1$ 条未画的边（因为环结构）
• 游戏过程是顺序打开链条的过程

关键观察：在一个连通分量中，游戏的进程可以被建模为：

• 分量由若干链条组成
• 每个链条打开时，会有一系列连续的得分机会
• 先手玩家（在当前分量中先行动的玩家）可以控制打开哪个链条

3. 链条的得分模式

考虑一个长度为 $L$ 的格子链条：

• 当玩家打开这个链条时，会立即得到1分并继续行动
• 然后双方交替在链条上画边，直到链条结束
• 在整个链条的争夺中，先手玩家会比后手玩家多得：
  • 如果 $L$ 是奇数：多得1分
  • 如果 $L$ 是偶数：多得0分

4. 连通分量的价值计算

对于一个连通分量：

1. 识别出所有的可用链条（即可以首先被打开的路径）
2. 计算每个链条的净得分优势（先手得分 - 后手得分）
3. 先手玩家会选择打开能给自己带来最大优势的链条

具体来说：

• 分量中的第一个行动者可以选择打开任意一个链条
• 打开链条后，该玩家立即得1分，并获得在该链条上的先手地位
• 然后双方在该链条上交替行动
• 链条处理完后，轮到对方在剩余部分先行动

5. 整体策略

由于现在是Anna先手：

1. 她首先选择价值最高的连通分量开始行动
2. 在每个分量内部，她选择最优的打开策略
3. 双方轮流选择分量进行游戏，直到所有边都被画完

算法步骤

1. 识别连通分量：

   • 通过DFS/BFS找出所有独立的连通分量
   • 记录每个分量包含的格子数

2. 分析分量结构：

   • 对于每个分量，找出所有可能的初始链条
   • 计算每个链条的净得分值

3. 计算分量价值：

   • 对于每个分量，计算在最优策略下的得分差
   • 这可以通过Minimax搜索或推导公式得到

4. 合并结果：

   • 将所有分量的价值求和
   • 注意玩家轮流选择分量的顺序

关键洞察

这道题的精妙之处在于：

• 利用"0或2条未画边"的条件将问题分解为独立分量
• 发现连通分量的环状结构特性
• 将复杂的网格博弈转化为链条得分的组合问题
• 应用组合博弈论的思想解决实际游戏问题

复杂度分析

• 识别连通分量：$O(NM)$
• 分析单个分量：与分量大小相关
• 由于 $N,M \leq 20$，总格子数不超过400，算法可行

这种解法充分利用了题目的特殊条件，将复杂的博弈问题转化为可管理的子问题，体现了组合博弈论在解决实际游戏问题中的强大能力。