「POI2009 R2」三角网格岛屿 题解

题目大意

在正三角形网格上，由若干个单位三角形组成的连通区域称为岛屿。每个岛屿可以用其边界路径的转角序列来编码，编码规则如下：

• 边界路径必须一次性描画完成（不抬笔）
• 岛屿内部始终在路径右侧（右旋描画）
• 使用5种转角类型：
  • a: 左转120°
  • b: 左转60°
  • c: 直行0°
  • d: 右转60°
  • e: 右转120°
• 编码为所有同构岛屿中字典序最小的边界描述

需要解决两类问题：

1. K查询：给定一个k三角形岛屿的编码，找出所有通过添加一个三角形得到的(k+1)三角形岛屿编码
2. N查询：找出所有n三角形岛屿的编码

算法分析

核心难点

1. 几何形状枚举：在三角网格上生成所有可能的连通形状
2. 同构判断：识别旋转、反射后相同的形状
3. 边界编码：将几何形状转换为规范的字符串表示
4. 字典序最小化：找到同构形状中最小的循环字符串表示

数据特征

根据测试数据，不同大小的岛屿数量为：

• 1三角形: 1个
• 2三角形: 1个
• 3三角形: 1个
• 4三角形: 3个
• 5三角形: 4个

形状扩展策略

1. 边界分析：找出所有可以添加三角形的边界位置
2. 连通性检查：确保添加后形状仍然连通
3. 重复检测：避免生成同构的形状
4. 编码规范化：为每个新形状生成最小编码

复杂度分析

• 时间复杂度：O(C(n))，其中C(n)是n三角形的岛屿数量
• 空间复杂度：O(C(n))，需要存储所有形状的编码

对于n ≤ 10，C(n)的值如下：

• C(1) = 1
• C(2) = 1
• C(3) = 1
• C(4) = 3
• C(5) = 4
• C(6) = 12
• C(7) = 24
• C(8) = 66
• C(9) = 159
• C(10) = 445

测试样例

输入:

2
K adeccecced
N 5

输出:

5
acedccecced addebcecced adebebecced adecbedcced cceccecce
4
aedddde bdecdde bececde ccedcde

总结

本题结合了计算几何、组合数学和字符串处理等多个领域：

• 使用三角网格坐标系表示形状
• 通过DFS生成所有可能的连通形状
• 利用字符串最小表示法规范化编码
• 基于预计算解决小规模问题

对于竞赛实践，推荐使用预计算打表法，既保证正确性又提高运行效率。