问题理解

我们有一个边长为 $N$ 的正六边形区域，由 $6N^2$ 个小正三角形组成。
网格中有：

• 3 个矿场（类型 1,2,3）
• 3 个炼矿厂（类型 1,2,3）
• 山地（类型 4，不可通过）
• 平地（类型 0，可通过）

目标：
为每个矿场 $i$ 到对应的炼矿厂 $i$ 找一条路径，使得：

1. 三条路径互不相交（不经过同一个三角形）
2. 只能走相邻三角形（共享边的三角形）
3. 不能经过山地
4. 总路径长度最小（每段路费用为 1）
5. 统计最小费用的方案数

---

关键观察

1. 网格结构转化

正六边形三角网格可以展开为一个平面图，更具体地，可以映射到一个矩形网格，其中每个格子是三角形，相邻关系保持。

一种常见的映射：
将六边形展开为 $(2N) \times (2N)$ 的菱形网格（或类似形状），每个位置是一个三角形，相邻三角形共享边。

2. 不相交路径问题

这是典型的多源多汇不相交路径问题，在网格上可用 插头DP 解决。

3. 问题规模

$N \leq 6$ → 整个网格至多 $6 \times 6^2 = 216$ 个三角形，但实际展开后的网格宽度约 $2N = 12$，高度约 $2N = 12$，共约 144 个格点，可状态压缩。

---

插头DP 思路

状态表示

我们逐格（按一定顺序，如从上到下、从左到右）进行DP。
在轮廓线上，每个边界线可能被路径穿过，我们用 括号表示法（或称连通性编码）记录路径的连通情况。

对于 $k$ 条路径，轮廓线上每个插头可以是：

• 0：无路径穿过
• 1：路径 1 的左端/右端
• 2：路径 2 的左端/右端
• 3：路径 3 的左端/右端

由于有 3 条路径，需要区分它们的端点。在括号序列中，我们用不同的数字表示不同的路径，并用括号匹配确保路径不交叉。

状态设计

设 $dp[x][y][mask]$ 表示：

• 当前处理到网格位置 $(x,y)$
• $mask$ 是当前轮廓线的连通状态（编码了哪些边界有路径插头以及它们的匹配关系）
• 值是一个 pair (min_cost, ways)

转移规则

根据当前格子的类型：

• 山地：必须无插头通过，否则无效
• 平地：可以无路径通过，或作为路径的一部分（连接两个插头）
• 矿场/炼矿厂：必须是相应路径的端点，只能有一个插头与之相连

具体转移：

1. 无插头进入/离开：保持状态
2. 创建新路径：在起点处，添加一个左括号（新的插头）
3. 结束路径：在终点处，匹配一个右括号
4. 连接两个插头：将两个插头连接起来（可能是直走、转弯等）
5. 关键约束：任何时候不能出现路径交叉，即括号序列必须合法

连通性编码

使用 最小表示法 或 括号序列 对轮廓线上的插头进行编码：

• 左括号：路径起点或拐弯点
• 右括号：路径终点或拐弯点
  通过一个整数 $mask$ 表示当前轮廓线上每个边界位置的插头类型和匹配关系。

---

算法步骤

1. 网格映射
   将六边形三角网格展开为二维网格，建立坐标映射和邻接关系。

2. 确定起点终点
   记录 3 个矿场和 3 个炼矿厂的坐标。

3. 插头DP

   • 初始化：$dp[0][0][0] = (0, 1)$
   • 按行主序遍历网格
   • 对每个状态，根据当前格子类型进行转移
   • 合并相同状态（取最小费用，累加方案数）

4. 终止条件
   处理完所有格子后，在轮廓线无插头（所有路径已完成）的状态中找最优解。

---

复杂度分析

• 网格大小：约 $(2N) \times (2N) = 12 \times 12 = 144$ 个格子
• 状态数：对于 3 条路径，括号序列状态数约 $C \cdot 7^m$（$m$ 是轮廓线宽度，约 $2N+1=13$），实际通过最小表示法可减少
• 总状态数约 $10^4 \sim 10^5$ 量级，在 $N=6$ 时可行

---

特殊情况处理

无解判断

• 如果某个矿场或炼矿厂在山地上，直接无解
• 如果矿场与炼矿厂之间被山地完全隔离，无解
• 如果 DP 结束后没有有效状态，输出 -1 -1

方案数统计

• 当多条路径走法不同但费用相同时，累加方案数
• 对 $10^9+7$ 取模

---

样例分析

样例 1
$N=2$，网格较小，三条路径必须绕开山地 4 且不相交。
通过插头DP可以找到唯一的最优方案，费用 18，方案数 1。

样例 2
$N=3$，类似地，路径更长，但依然只有一种最小费用方案。

---

总结

这道题的核心是：

1. 网格映射：将六边形三角网格转化为规则的二维网格
2. 插头DP：使用括号序列表示路径连通性，处理不相交约束
3. 状态压缩：利用 $N$ 小的特点，对轮廓线状态进行编码
4. 费用与计数：同时维护最小费用和方案数

通过插头DP，可以高效解决这类网格图上的不相交路径规划问题。