【題目大意】
題目的大意是給定一個(gè)由許多六面形邊挨著邊組成的圖形，從中心處開(kāi)始標(biāo)號(hào)為1，按照一個(gè)螺旋的方向標(biāo)號(hào)依次增加。問(wèn)從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的最短路徑的長(zhǎng)度和數(shù)目。
【算法分析】
感覺(jué)滿惡心的一個(gè)題目，需要瘋狂的找規(guī)律。首先容易看出路徑數(shù)是一個(gè)組合數(shù)，并且每一層都是模六循環(huán)的。但是怎樣找到層數(shù)（也就是最短路徑長(zhǎng)度）呢？最開(kāi)始想建立坐標(biāo)系然后利用幾何方法算出來(lái)，但是如何無(wú)論是笛卡爾坐標(biāo)系還是極坐標(biāo)系的建立都是困難的；然后想存圖廣搜，發(fā)現(xiàn)空間不夠。后來(lái)發(fā)現(xiàn)，把圖順時(shí)針轉(zhuǎn)90度，出現(xiàn)了一個(gè)很有意思的規(guī)律。以原點(diǎn)（數(shù)字為1）為中心建立坐標(biāo)系，不過(guò)坐標(biāo)的選取需要一些技巧。可以看出數(shù)字是一層層分布的，取x左邊的點(diǎn)坐標(biāo)為（-2，0），以后每往左增加一層，橫坐標(biāo)就變化2。其實(shí)和原點(diǎn)縱坐標(biāo)相同且位于其左邊的點(diǎn)恰好是每一層數(shù)字最大的結(jié)點(diǎn)！這樣只要確定了這個(gè)點(diǎn)，可以按照逆時(shí)針的順序依次給這一層的所有點(diǎn)的坐標(biāo)推出來(lái)。這樣，給定一個(gè)數(shù)字，我們可以根據(jù)每一層最大的數(shù)字推出這個(gè)數(shù)的坐標(biāo)。
現(xiàn)在有了坐標(biāo)（可以看成是曼哈頓坐標(biāo)），就可以推測(cè)路徑了。把兩個(gè)數(shù)字的坐標(biāo)求差，就可以看成是一個(gè)在原點(diǎn)了。坐標(biāo)和路徑的關(guān)系不是很好找，寫(xiě)了4、5行發(fā)現(xiàn)了一個(gè)很詭異的規(guī)律。先把坐標(biāo)化成正的，然后發(fā)現(xiàn)x >= y的時(shí)候就是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 閱讀(404)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
Algorithm - Combinatorics