如下图所示，蜂窝小区，以1为中心，顺时针编号，编号最大限定为100000。
求任意两编号之间的最短距离。
两个相邻小区的距离为1
示例：19到30的最短距离为5
实现如下三个接口：
/************************************************************************
Description : 初始化蜂窝小区信息
Prototype : void InitCellularDistrict(int iMaxSeqValue)
Input Param : iMaxSeqValue 蜂窝小区的最大值编号，注：编号从1开始
Output Param : 无
Return Value : 成功返回0，失败返回-1
/************************************************************************/
int InitCellularDistrict(int iMaxSeqValue)
{
return -1;
}
/************************************************************************
Description : 计算出蜂窝小区指定两点（编号值）之间的最短距离
Prototype : int GetShortestPathLength(int iFirstValue, int iSecondValue)
Input Param : iFirstValue 起点编号值， iSecondValue 终点编号值
Output Param : 无
Return Value : 计算成功返回最短距离，失败返回-1
/************************************************************************/
int GetShortestPathLength(int iFirstValue, int iSecondValue)
{
return -1;
}
/************************************************************************
Description : 清空相关信息
Prototype : void Clear()
Input Param : 无
Output Param : 无
Return Value : 无
/************************************************************************/
void Clear()
{
}
解题思路：
1、约定：定义XYZ坐标如上图所示，X轴往左平移n个单位定义为x=-n，往右平移n个单位则定义为x=n，同理，Y轴往左上平移n个单位定义为y=n，Y轴往右下平移n个单位定义为y=-n，Z轴往右上平移n个单位定义为z=n，Z轴往左下平移n个单位定义为z=-n。如下图所示：
2、定义点坐标：有了前面的约定，整个区域内的任何一个点都可以从序号为1的蜂窝开始沿坐标轴垂直方向多次移动到达。然后我们就可以定义每个点坐标如何表示了，如下图所示：
我们取29这个点来举例说明，它所在X轴左平移2个单位处，因此x=-2，它所在Y轴左上平移3个单位处，因此y=3，最后你会发现Z已经定死了，即它所在Z轴右上平移1个单位处，因此z=1。这样，我们就得到了29这个点的XYZ坐标表示：29(-2，3，1)。
3、计算任意点p的XYZ坐标表示：上面我们取了29这个点来举例说明如何能XYZ坐标表示一个点，现在我们要用XYZ坐标来表示任意点p，
3.1、首先，我们先计算点p在第几个圆环上，通过上图我们可以直观看到点1在第0环，点7在第1环，点19在第2环，点37在第3环，……，点p在第几环？仔细观察不难发现有个规律，第0环共有1个点，第1环共有6个点，第2环共有12个点，第3环共有18个点，……，每一环都比前一环多6个点（第0、1环除外），有这个规律后就好办了，点p在第几环(i)就可以这样判断了：
cpp代码
int i = 0, v = 1;
//find the ring (i) that ·p‘ belongs to.
for (; v<p; v+=6*(++i))
;
//finding finish
3.2、得到点p在第几个圆环上还不够的，我们还要知道点p在圆环的第几条边上，显然这里一个圆环有6条边(第0环除外)，我们不妨按下图来定义边的序号(下图定义边的序号比较方便计算p所在的边，当然从1开始也无妨)：
那么，计算p所在的边就可以用下面的方法：
cpp代码
//v就是前面计算出来的v，代表i环及前面所有环的点个数，i就是p所在圆环。(比如点29在第3环，第3环、第2环、第1环、第0环这四环总共有37个点，那么点29所在的边就是(37-29)/3,等于2，即第2边)
int side = (v-p)/i;
3.3、知道到点p所在圆环，也知道了点p所在边，最后还需要知道一个东西，就是点p在所在边的哪个位置上，先看下图：
我们这个图来举例说明点p所在边(side)的位置(step)，比如点37，它在第0边的第0个位置，点36在第0边的第1个位置，点35在第0边的第2个位置，点34在第1边的第0个位置，……，计算方法如下：
cpp代码
//各变量含意同上
int step = (v-p)%i;
3.4、现在我们知道了点p所在圆环、所在边、所在边上的位置，要得到其XYZ坐标就简单了，废话不多说，直接看代码(聪明的你一定可以发现，只要确定了XYZ中任意两者，第三个值也就定死了)：
cpp代码
switch (side)
{
case 0: x = i; y = -i+step; z = x+y; break;
case 1: z = i; y = step; x = z-y; break;
case 2: y = i; z = i-step; x = z-y; break;
case 3: x = -i; y = i-step; z = x+y; break;
case 4: z = -i; y = -step; x = z-y; break;
case 5: y = -i; z = -i+step; x = z-y; break;
default: break;
}
4、计算最短距离：有了任意两点p1,p2的XYZ坐标表示，计算它们间的最短距离就简单了，原因很简单，最短距离就是p1,p2两点的x,y,z差值最小的两者之和，或换个说法就是这两点的x,y,z差值最大的那个。（因为在平面图上两个坐标就能确定一个点，其实使用了三维坐标，那第三个坐标一定是和通过前两个坐标就能计算的出）
最后附上参考cpp代码：
#include "CellularDistrict.h"
struct POS
{
POS(int val):x(0),y(0),z(0)
{
int i = 0, v = 1;
//find the ring (i) that val belongs to.
for (; v<val; v+=6*(++i));
//get x,y,z;
if(i > 0)
{
int side = (v-val)/i;
int step = (v-val)%i;
switch (side)
{
case 0: x = i; y = -i+step; z = x+y;break;
case 1: z = i; y = step; x = z-y;break;
case 2: y = i; z = i-step; x = z-y;break;
case 3: x = -i; y = i-step; z = x+y;break;
case 4: z = -i; y = -step; x = z-y;break;
case 5: y = -i; z = -i+step; x = z-y;break;
default: break;
}
}
}
int operator - (const POS &p) const
{
int i = x>p.x ? x-p.x : p.x-x;
int j = y>p.y ? y-p.y : p.y-y;
int k = z>p.z ? z-p.z : p.z-z;
return i>j ? (i>k?i:k) : (j>k?j:k);
}
private:
int x, y, z;
};
static int g_max;
/************************************************************************
Description : 初始化蜂窝小区信息
Prototype : void InitCellularDistrict(int iMaxSeqValue)
Input Param :iMaxSeqValue 蜂窝小区的最大值编号，注：编号从1开始
Output Param : 无
Return Value : 成功返回0，失败返回-1
/************************************************************************/
int InitCellularDistrict(int iMaxSeqValue)
{
if (iMaxSeqValue>0 && iMaxSeqValue<=100000)
{
g_max = iMaxSeqValue;
return 0;
}
return -1;
}
/************************************************************************
Description : 计算出蜂窝小区指定两点（编号值）之间的最短距离
Prototype : int GetShortestPathLength(int iFirstValue, intiSecondValue)
Input Param :iFirstValue 起点编号值， iSecondValue 终点编号值
Output Param : 无
Return Value : 计算成功返回最短距离，失败返回-1
/************************************************************************/
int GetShortestPathLength(int iFirstValue, int iSecondValue)
{
if (0<iFirstValue && iFirstValue<=g_max
&& 0<iSecondValue &&iSecondValue<=g_max)
{
POS first(iFirstValue), second(iSecondValue);
return first-second;
}
return -1;
}
/************************************************************************
Description : 清空相关信息
Prototype : void Clear()
Input Param : 无
Output Param : 无
Return Value : 无
/************************************************************************/
void Clear()
{
g_max = 0;
}