蜂窝小区最短距离

package tt;

 

/**

 * 蜂窝小区，以1为中心，顺时针编号，编号最大限定为100000。 求任意两编号之间的最短距离。 两个相邻小区的距离为1

 *

 * 参见试题说明的示意图

 *

 */

public class CellularDistrict {

 

private int maxSeq = 0;

 

private Point firstPoint;

 

private Point secondPoint;

 

/**

* 

* 初始化蜂窝小区信息

* 

*

* 

* @param iMaxSeqValue

* 

*            蜂窝小区的最大值编号，注：编号从1开始

* 

* @return 成功返回0，失败返回-1

*/

 

public int initCellularDistrict(int iMaxSeqValue) {

 

if (iMaxSeqValue > 0 && iMaxSeqValue <= 100000) {

 

this.maxSeq = iMaxSeqValue;

 

return 0;

 

}

 

return -1;

 

}

 

/**

* 

* 计算出蜂窝小区指定两点（编号值）之间的最短距离

* 

*

* 

* @param iFirstValue

* 

*            起点编号值

* 

* @param iSecondValue

* 

*            终点编号值

* 

* @return 计算成功返回最短距离，失败返回-1

*/

 

public int getShortestPathLength(int iFirstValue, int iSecondValue) {

 

if (0 < iFirstValue && iFirstValue <= this.maxSeq && 0 < iSecondValue

 

&& iSecondValue <= this.maxSeq) {

 

firstPoint = new Point(iFirstValue);

 

secondPoint = new Point(iSecondValue);

 

return firstPoint.minus(secondPoint);

 

}

 

return -1;

 

}

 

/**

* 

* 清空相关信息

*/

 

public void clear() {

 

maxSeq = 0;

 

firstPoint = null;

 

secondPoint = null;

 

}

 

private class Point {

 

private int x;

 

private int y;

 

private int z;

 

/**

* 

* 

* 构造方法

*/

 

Point(int seqValue) {

 

// 点在哪一个圈

 

int i = 0;

 

// 点所在圈序号最大的点

 

int v = 1;

 

// 查找给定点是属于哪一个圈

 

for (; v < seqValue; v += 6 * (++i))

 

;

 

// 获取点的x、y和z坐标

 

if (i > 0) {

 

// 点在圈的哪一条边

 

int side = (v - seqValue) / i;

 

// 点在边的位置

 

int step = (v - seqValue) % 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 minus(Point p) {

 

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);

 

}

 

}

}