MYF

HDU 1030 Delta-wave

Posted on | In | | Visitors

题目链接

HDU 1030

解题方法：建立坐标系找关系

题目分析

题目大意

规则：只能穿过边，不能穿过点。问从三角形x到三角形y最少需要几步。

解析

对于每一个小三角形，只能向其三边的邻接三角形移动，所以可以按图建立坐标系。

其中对于x轴来讲，竖着看从上到下每一层的坐标是1,2,3,4…

对于y轴，则第一层有1,3,2,6,5,11,10，第二层有4,8,7,13,12，以此类推。

对于z轴，则第一层有1,3,4,8,9,15,16，第二层有2,6,7,13,14，以此类推。

所以每一个点都可以由(x,y,z)唯一表示，任意两点间的距离是对应方向坐标的差之和，即为所求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int main(){
    int a,b,x1,y1,z1,x2,y2,z2;
    while (scanf("%d %d",&a,&b)!=EOF) {
        x1=ceil(sqrt(a));
        x2=ceil(sqrt(b));
        y1=ceil((a-(x1-1)*(x1-1))/2.0);
        y2=ceil((b-(x2-1)*(x2-1))/2.0);
        z1=ceil((x1*x1-a+1)/2.0);
        z2=ceil((x2*x2-b+1)/2.0);
        printf("%d\n",abs(x1-x2)+abs(y1-y2)+abs(z1-z2));
    }
}