题目描述蜂窝中的蜂房按顺时针顺序从111开始编号形成一个六边形网格蜂巢结构。给定两个蜂房编号aaa和bbba,b≤10000a, b \le 10000a,b≤10000要求计算它们之间的最短路径长度即从一个蜂房移动到相邻蜂房的最少步数。输入包含多组数据以0 0结束。输入格式输入包含若干行每行两个整数aaa和bbb表示两个蜂房编号。输入以0 0结束。输出格式对于每对(a,b)(a,b)(a,b)输出一行格式为The distance between cells a and b is d.其中ddd为最短距离。样例输入19 30 0 0样例输出The distance between cells 19 and 30 is 5.题目分析蜂窝网格是六边形密铺结构每个蜂房有666个相邻蜂房。编号按螺旋顺序从中心向外扩展。要计算任意两编号之间的最短距离可将每个编号映射到二维坐标上然后计算坐标之间的六边形网格距离。在六边形网格中若两点坐标为(x1,y1)(x_1, y_1)(x1,y1)和(x2,y2)(x_2, y_2)(x2,y2)则其最短步数为若(x1−x2)⋅(y1−y2)0(x_1 - x_2) \cdot (y_1 - y_2) 0(x1−x2)⋅(y1−y2)0则距离为max(∣dx∣,∣dy∣)\max(|dx|, |dy|)max(∣dx∣,∣dy∣)否则距离为∣dxdy∣|dx dy|∣dxdy∣。因此首要任务是为每个编号确定其在二维平面上的坐标。解题思路采用逐层构建的方法。编号111位于中心坐标为(0,0)(0,0)(0,0)。第kkk层k≥1k \ge 1k≥1包含6k6k6k个蜂房编号范围为[13k(k−1),13k(k1)][1 3k(k-1), 1 3k(k1)][13k(k−1),13k(k1)]。例如第111层编号222到777第222层编号888到191919依此类推。构建过程确定第kkk层的起始编号start13k(k−1)start 1 3k(k-1)start13k(k−1)。该层的右上顶点坐标为(0,k)(0, k)(0,k)对应的编号为startstartstart当k≥1k \ge 1k≥1时startstartstart确实在最上方。从该顶点开始按顺时针方向六个方向遍历该层的6k6k6k个蜂房依次赋予坐标。方向依次为左上(−1,0)(-1,0)(−1,0)、左(0,−1)(0,-1)(0,−1)、左下(1,−1)(1,-1)(1,−1)、右下(1,0)(1,0)(1,0)、右(0,1)(0,1)(0,1)、右上(−1,1)(-1,1)(−1,1)每个方向走kkk步。由于a,b≤10000a, b \le 10000a,b≤10000最大层数满足13k(k1)≥100001 3k(k1) \ge 1000013k(k1)≥10000解得k≈58k \approx 58k≈58因此可直接预计算所有编号的坐标。代码实现// Bee Breeding// UVa ID: 808// Verdict: Accepted// Submission Date: 2018-03-14// UVa Run Time: 0.020s//// 版权所有C2018邱秋。metaphysis # yeah dot net//// Similar to UVa 10182.#includebits/stdc.husingnamespacestd;constintMAXN10000;intoffset[5][2]{{-1,0},{0,-1},{1,-1},{1,0},{0,1}};pairint,intmaja[MAXN2000];intmain(intac,char*av[]){for(inti1,j1,k0;iMAXN;ij,j6,k){maja[i]make_pair(0,k);for(intm0;mk;m)maja[i-m]make_pair(m,k-m);intcurrenti;for(intm0;m5;m)for(intn0;nk;n){intxmaja[current].firstoffset[m][0];intymaja[current].secondoffset[m][1];maja[current1]make_pair(x,y);current;}}inta,b,d;while(cinab){if(a0b0)break;pairint,intvmake_pair(maja[a].first-maja[b].first,maja[a].second-maja[b].second);if(v.first*v.second0)dmax(abs(v.first),abs(v.second));elsedabs(v.firstv.second);coutThe distance between cells a and b is d.\n;}return0;}总结本题通过将蜂房编号映射到六边形网格的二维坐标将最短路径问题转化为六边形坐标下的距离计算。预计算所有编号的坐标查询时直接差分并应用六边形距离公式。关键在于正确理解编号的螺旋排列规律并逐层生成坐标。该解法时间复杂度O(N)O(\sqrt{N})O(N)用于预计算查询O(1)O(1)O(1)适用于N≤10000N \le 10000N≤10000的数据规模。六边形距离公式的推导是解题的核心。 
长河君 · 2026/9/4 5:47:17 · 阅读 1.2k UVa 808 Bee Breeding
题目描述蜂窝中的蜂房按顺时针顺序从111开始编号形成一个六边形网格蜂巢结构。给定两个蜂房编号aaa和bbba,b≤10000a, b \le 10000a,b≤10000要求计算它们之间的最短路径长度即从一个蜂房移动到相邻蜂房的最少步数。输入包含多组数据以0 0结束。输入格式输入包含若干行每行两个整数aaa和bbb表示两个蜂房编号。输入以0 0结束。输出格式对于每对(a,b)(a,b)(a,b)输出一行格式为The distance between cells a and b is d.其中ddd为最短距离。样例输入19 30 0 0样例输出The distance between cells 19 and 30 is 5.题目分析蜂窝网格是六边形密铺结构每个蜂房有666个相邻蜂房。编号按螺旋顺序从中心向外扩展。要计算任意两编号之间的最短距离可将每个编号映射到二维坐标上然后计算坐标之间的六边形网格距离。在六边形网格中若两点坐标为(x1,y1)(x_1, y_1)(x1,y1)和(x2,y2)(x_2, y_2)(x2,y2)则其最短步数为若(x1−x2)⋅(y1−y2)0(x_1 - x_2) \cdot (y_1 - y_2) 0(x1−x2)⋅(y1−y2)0则距离为max(∣dx∣,∣dy∣)\max(|dx|, |dy|)max(∣dx∣,∣dy∣)否则距离为∣dxdy∣|dx dy|∣dxdy∣。因此首要任务是为每个编号确定其在二维平面上的坐标。解题思路采用逐层构建的方法。编号111位于中心坐标为(0,0)(0,0)(0,0)。第kkk层k≥1k \ge 1k≥1包含6k6k6k个蜂房编号范围为[13k(k−1),13k(k1)][1 3k(k-1), 1 3k(k1)][13k(k−1),13k(k1)]。例如第111层编号222到777第222层编号888到191919依此类推。构建过程确定第kkk层的起始编号start13k(k−1)start 1 3k(k-1)start13k(k−1)。该层的右上顶点坐标为(0,k)(0, k)(0,k)对应的编号为startstartstart当k≥1k \ge 1k≥1时startstartstart确实在最上方。从该顶点开始按顺时针方向六个方向遍历该层的6k6k6k个蜂房依次赋予坐标。方向依次为左上(−1,0)(-1,0)(−1,0)、左(0,−1)(0,-1)(0,−1)、左下(1,−1)(1,-1)(1,−1)、右下(1,0)(1,0)(1,0)、右(0,1)(0,1)(0,1)、右上(−1,1)(-1,1)(−1,1)每个方向走kkk步。由于a,b≤10000a, b \le 10000a,b≤10000最大层数满足13k(k1)≥100001 3k(k1) \ge 1000013k(k1)≥10000解得k≈58k \approx 58k≈58因此可直接预计算所有编号的坐标。代码实现// Bee Breeding// UVa ID: 808// Verdict: Accepted// Submission Date: 2018-03-14// UVa Run Time: 0.020s//// 版权所有C2018邱秋。metaphysis # yeah dot net//// Similar to UVa 10182.#includebits/stdc.husingnamespacestd;constintMAXN10000;intoffset[5][2]{{-1,0},{0,-1},{1,-1},{1,0},{0,1}};pairint,intmaja[MAXN2000];intmain(intac,char*av[]){for(inti1,j1,k0;iMAXN;ij,j6,k){maja[i]make_pair(0,k);for(intm0;mk;m)maja[i-m]make_pair(m,k-m);intcurrenti;for(intm0;m5;m)for(intn0;nk;n){intxmaja[current].firstoffset[m][0];intymaja[current].secondoffset[m][1];maja[current1]make_pair(x,y);current;}}inta,b,d;while(cinab){if(a0b0)break;pairint,intvmake_pair(maja[a].first-maja[b].first,maja[a].second-maja[b].second);if(v.first*v.second0)dmax(abs(v.first),abs(v.second));elsedabs(v.firstv.second);coutThe distance between cells a and b is d.\n;}return0;}总结本题通过将蜂房编号映射到六边形网格的二维坐标将最短路径问题转化为六边形坐标下的距离计算。预计算所有编号的坐标查询时直接差分并应用六边形距离公式。关键在于正确理解编号的螺旋排列规律并逐层生成坐标。该解法时间复杂度O(N)O(\sqrt{N})O(N)用于预计算查询O(1)O(1)O(1)适用于N≤10000N \le 10000N≤10000的数据规模。六边形距离公式的推导是解题的核心。