题意分析

问题背景

卡车司机需要在正六边形网格地图上找到两个单元之间的最短路径，并统计相同长度的不同路径数量。这有助于节省运输成本，并为道路施工等情况提供备用路线。

地图与单元

• 地图由正六边形网格构成，每个单元从 $1$ 开始按螺旋方式编号。
• 每个单元有 $6$ 个相邻单元（共享一条边的单元相邻）。
  • 例如：单元 $2$ 的邻居是 $1$、$3$、$7$、$8$、$9$、$10$。

路线定义

• 六边形路线：非空单元序列，除最后一个单元外，每个单元与后继单元相邻。
• 路线长度：序列长度减 $1$（即移动步数）。
• 最短路径：所有可能路线中长度最小的路径。

输入输出要求

• 输入：多组测试用例，每行两个整数 $X$ 和 $Y$（$1 \leq X, Y \leq 1,000,000$），以 $0\ 0$ 结束。
• 输出：
  • 若最短路径唯一：
    There is 1 route of the shortest length L.
  • 若有多条最短路径：
    There are N routes of the shortest length L.

---

解题思路

1. 构建坐标系统

将螺旋编号映射到六边形网格坐标 $(x, y)$，便于计算距离和路径。

• 分层规则：
  • 第 $1$ 层：$1$（中心单元）。
  • 第 $n$ 层：$6(n-1)$ 个单元（编号范围 $2$ 到 $7$ 为第 $2$ 层，$8$ 到 $19$ 为第 $3$ 层，依此类推）。
• 坐标计算：
  • 通过层数 $n$ 和单元在层中的位置 $p$ 确定坐标。例如：
    • 单元 $1$：$(0, 0)$。
    • 单元 $2$：$(1, 0)$，单元 $3$：$(0, 1)$，单元 $4$：$(-1, 1)$，等等。

2. 计算最短路径长度

六边形网格中的距离公式：

$$L = \max(|x_1 - x_2|, |y_1 - y_2|, |(x_1 + y_1) - (x_2 + y_2)|) $$

或等效形式：

$$L = \frac{|x_1 - x_2| + |y_1 - y_2| + |(x_1 + y_1) - (x_2 + y_2)|}{2} $$

3. 统计最短路径数量

• 关键观察：最短路径的数量取决于坐标差的组合方式。
  • 若 $\Delta x \cdot \Delta y \geq 0$，路径数为组合数 $\binom{L}{\Delta x}$ 或 $\binom{L}{\Delta y}$。
  • 否则，需考虑对称性调整。
• 示例：
  • 单元 $1$ 到 $8$：坐标 $(0, 0)$ 到 $(2, 0)$，$L=2$，路径数 $2$（两种对称路径）。

4. 算法实现

1. 编号转坐标：
   • 计算层数 $n$ 和位置 $p$，转换为 $(x, y)$。
2. 距离计算：
   • 使用六边形距离公式求 $L$。
3. 路径计数：
   • 根据坐标差计算组合数 $N$。

---

示例分析

• 输入：1 2

  • 坐标：$(0, 0)$ 到 $(1, 0)$，$L=1$，$N=1$。
  • 输出：There is 1 route of the shortest length 1.

• 输入：1 8

  • 坐标：$(0, 0)$ 到 $(2, 0)$，$L=2$，$N=2$。
  • 输出：There are 2 routes of the shortest length 2.

• 输入：1000 9000

  • 大数需高效计算，$L=73$，$N=278940769844931007968$。
  • 输出：There are 278940769844931007968 routes of the shortest length 73.

---

总结

1. 坐标转换：将编号映射到六边形坐标。
2. 距离计算：使用六边形几何性质求最短路径长度 $L$。
3. 路径计数：通过组合数学或动态规划统计路径数 $N$。
4. 输出结果：根据 $N$ 的值选择单数或复数形式输出。

标程