蜂窝小区最短距离的坐标系解法（java代码）

需求和算法分析请看：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));
    }

    

}