2013-07-18 10:03:42Morris
[UVA][討論] 10022 - Delta-wave
Delta-wave
| Delta-wave |
On the triangular field shown on the picture, small triangles are
numbered from 1 to oo (infinity). Traveller wants to go from triangle M
to triangle N. Traveller can move only through the sides of triangles,
not vertices. The number of sides he crosses is called the path length.
You are to determine the shortest path from M to N.
The Input
The first line is the number of test cases, followed by a blank line.
Each test case of the input contains integers M and N (1<=M,N<=1000000000), separated by some spaces.
Each test case will be separated by a single line.
The Output
For each test case, your programm should print the length of the shortest path from M to N.
Print a blank line between the outputs for two consecutive test cases.
Sample Input
1 6 12
Sample Output
3
Alex Gevak
September 10, 2000 (Revised 2-10-00, Antonio Sanchez)
題目要求很簡單，找一條最短路。
分類前，先定義座標方式。
(1,1)
(2,1)(2,2)(2,3)
(3,1)(3,2)(3,3)(3,4)(3,5)
...
(p, q), p 表示第幾層，q 則是該層的第幾個。
很容易地發現 q 是奇數的時候是上三角形，偶數時是下三角形。
然後最短路規劃，一律從最上層走到最下層。
分類有四種可能
(1) 上三角形走到上三角形
(2) 上三角形走到下三角形
(3) 下三角形走到上三角形
(4) 下三角形走到下三角形
定義 A(a,b)->B(p, q) // a <= p
則在
(1) 如果 B 在 A 的大三角形內部的話(將 A 延長的三角形)，最短路長為 (p-a)*2
(2) 如果 B 在 A 的大三角形內部的話(將 A 延長的三角形)，最短路長為 (p-a)*2-1
(1)(2) 如果 B 不在其中的話，移動 B 的水平位置，讓它符合上述兩種情況。
跑 O(sqrt(n)) 找最小值。
接著討論 (3)(4)
(3)(4) 考慮移動 A 的水平位置，且A的位置是上三角形，去符合 (1)(2) 的情況。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
void getXY(int n, int &x, int &y) {
int h = 1;
while(true) {
if(h*h >= n)break;
h++;
}
x = h;
y = n-(x-1)*(x-1);
}
int path(int px, int py, int qx, int qy) {
if(px == qx) return abs(py-qy);
int ret = 0xffffff;
if(py&1) {// forward triangle
int x = qx, y = 1;
while(y <= 2*x-1) {
if(py <= y && y <= py+2*(qx-px)) {
if(y&1) {//forward triangle
ret = min(ret, 2*(x-px)+abs(y-qy));
} else {
ret = min(ret, 2*(x-px)+abs(y-qy)-1);
}
}
y++;
}
} else {
int x = px, y = 1;
while(y <= 2*x-1) {
if(y <= qy && qy <= y+2*(qx-px)) {
if(qy&1) {//forward triangle
ret = min(ret, 2*(qx-x)+abs(y-py));
} else {
ret = min(ret, 2*(qx-x)+abs(y-py)-1);
}
}
y += 2;
}
}
return ret;
}
int main() {
int testcase;
int n, m;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
if(n > m) swap(n, m);
int px, py, qx, qy;
getXY(n, px, py);
getXY(m, qx, qy);
//printf("%d %d %d %d\n", px, py, qx, qy);
int ret = path(px, py, qx, qy);
printf("%d\n", ret);
if(testcase)
puts("");
}
return 0;
}