蜂巢小区最短距离的坐标系解法(java代码)
蜂窝小区最短距离的坐标系解法(java代码)
需求和算法分析请看:http://blog.csdn.net/nys001/article/details/12637201
实现类:
测试类:
需求和算法分析请看:http://blog.csdn.net/nys001/article/details/12637201
实现类:
/** * 蜂窝小区,以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); } } }
测试类:
import junit.framework.TestCase; public class CellularDistrictTest extends TestCase { private CellularDistrict cellularDistrict = new CellularDistrict(); protected void setUp() throws Exception { super.setUp(); } protected void tearDown() throws Exception { super.tearDown(); cellularDistrict.clear(); } public void testCase1() { assertEquals(0, cellularDistrict.initCellularDistrict(30)); assertEquals(5, cellularDistrict.getShortestPathLength(19, 30)); } }