【題目大意】
題目的大意是給定一個由許多六面形邊挨著邊組成的圖形，從中心處開始標號為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 閱讀(398)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics