【题目大意】
题目的大意是给定一个由许多六面形边挨着边组成的图形，从中心处开始标号为1，按照一个螺旋的方向标号依次增加。问从一个点到另一个点的最短路径的长度和数目。
【算法分析】
感觉满恶心的一个题目，需要疯狂的找规律。首先容易看出路径数是一个组合数，并且每一层都是模六循环的。但是怎样找到层数（也就是最短路径长度）呢？最开始想建立坐标系然后利用几何方法算出来，但是如何无论是笛卡尔坐标系还是极坐标系的建立都是困难的；然后想存图广搜，发现空间不够。后来发现，把图顺时针转90度，出现了一个很有意思的规律。以原点（数字为1）为中心建立坐标系，不过坐标的选取需要一些技巧。可以看出数字是一层层分布的，取x左边的点坐标为（-2，0），以后每往左增加一层，横坐标就变化2。其实和原点纵坐标相同且位于其左边的点恰好是每一层数字最大的结点！这样只要确定了这个点，可以按照逆时针的顺序依次给这一层的所有点的坐标推出来。这样，给定一个数字，我们可以根据每一层最大的数字推出这个数的坐标。
现在有了坐标（可以看成是曼哈顿坐标），就可以推测路径了。把两个数字的坐标求差，就可以看成是一个在原点了。坐标和路径的关系不是很好找，写了4、5行发现了一个很诡异的规律。先把坐标化成正的，然后发现x >= y的时候就是C( (x + y) / 2, y)，否则是C( y, (y - x) / 2)。之后就是高精度了。
题目代码：
1 import java.util.*;
2 import java.math.*;
3
4 class point
5 {
6 int x, y;
7 public point(int x, int y)
8 {
9 this.x = x;
10 this.y = y;
11 }
12 }
13 class Main
14 {
15 public static void main(String[] args)
16 {
17 Scanner in = new Scanner(System.in);
18 int a, b, len;
19 BigInteger ans;
20 point pa, pb;
21
22 while (in.hasNext())
23 {
24 a = in.nextInt();
25 b = in.nextInt();
26 if (a == 0 && b == 0)
27 break;
28 pa = GetCoordinate(a);
29 pb = GetCoordinate(b);
30 pa.x = pb.x - pa.x;
31 pa.y = pb.y - pa.y;
32 pa.x = pa.x < 0 ? -pa.x : pa.x;
33 pa.y = pa.y < 0 ? -pa.y : pa.y;
34 if (pa.x >= pa.y)
35 {
36 len = (pa.x + pa.y) / 2;
37 ans = C(len, pa.y);
38 }
39 else
40 {
41 len = pa.y;
42 ans = C(len, (pa.y - pa.x) / 2);
43 }
44 System.out.print("There ");
45 if (ans.compareTo(BigInteger.ONE) == 0)
46 System.out.print("is 1 route");
47 else
48 System.out.print("are " + ans + " routes");
49 System.out.println(" of the shortest length " + len + ".");
50 }
51 }
52 static BigInteger C(int n, int k)
53 {
54 BigInteger ret = BigInteger.ONE;
55 if (k > n - k)
56 k = n - k;
57 for (int i = 1; i <= k; i++)
58 {
59 ret = ret.multiply(new BigInteger(new String(n - i + 1 + "")));
60 ret = ret.divide(new BigInteger(new String(i + "")));
61 }
62 return ret;
63 }
64 static point GetCoordinate(int n)
65 {
66 int[][] dir = new int[][]{{1, -1}, {2, 0}, {1, 1}, {-1, 1}, {-2, 0}, {-1, -1}};
67 int i = 0, j = 0, k = 0, tx, ty, cnt = 0, delta;
68 point p = new point(0, 0);
69
70 if (n == 1)
71 return p;
72 for (i = 2; i <= 1000; i++)
73 if ((3 * i * i - 3 * i + 1) >= n)
74 break;
75 delta = 3 * i * i - 3 * i + 1 - n;
76 i--;
77 tx = -2 * i;
78 ty = 0;
79 boolean flag = false;
80 for (j = 0; j < 6; j++)
81 {
82 for (k = 0; k < i; k++)
83 {
84 if (cnt == delta)
85 {
86 flag = true;
87 break;
88 }
89 cnt++;
90 tx += dir[j][0];
91 ty += dir[j][1];
92 }
93 if (flag)
94 break;
95 }
96 p.x = tx;
97 p.y = ty;
98
99 return p;
100 }
101 }
102
posted on 2009-06-16 22:12
sdfond 阅读(372)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Combinatorics