[uva 10642] Can You Solve It? – hwchang0417
給定source和destination的座標，試計算中間必須經過多少次邊界，座標走訪必須試沿+x, +y座標上的Z字形走訪。
Programming Language: C
Solution:
列出(0, 0)到(4, 0)的所有邊界次數
(0, 0) => 0
(0, 1) => 1
(1, 0) => 2
(0, 2) => 3
(1, 1) => 4
(2, 0) => 5
(0, 3) => 6
(1, 2) => 7
(2, 1) => 8
(3, 0) => 9
(0, 4) => 10
發現當y等於3時，3 * 2 = 6，當y等於4，4 * 2.5=10，其距離間距呈現下列關係:
(倍率 = 1 + 0.5f * (y – 1))，爾後x每增加一個座標，邊界次數加一，故公式改為:
steps(n, x) = (1 + 0.5f * (n – 1)) * n + x，其中n為x+y
於是可以用下列方式求得source到destination的邊界走訪次數
n1 = x1 + y1; n2 = x2 + y2;
ans = steps(n2, x2) – steps(n1, x1);
steps(n, x) = (1 + 0.5f * (n – 1)) * n + x
Read full article from [uva 10642] Can You Solve It? – hwchang0417
No comments:
Post a Comment