UVa808 Bee Breeding(坐标转换技巧)

蜂窝的样子
这题坑了我好长时间…建图方法问了某神犇,然后发现他建的图我无法求出解(因为我太辣鸡了吧),然后就自己改了图,大概长这个鬼样子:

按照蜂窝建成的网格图的样子
建图原理就是,原蜂窝中相邻的也要相邻,把六边形转化为网格里的形式,就是要使得至少每个点相邻的六个点在网格中可到达。在这个图中,只要是有一个点相接的格子,都是可到达的,也就是说,以下六个方向为可达的点:

$$(1,1),(0,2),(-1,1),(1,-1),(0,-2),(-1,-1)$$

但是实际上如果要求两点间距离,肯定不能去这样搜索,那会超时。所以考虑直接通过坐标加减求得答案。

假定给你的点为$a,b$,设$a(x_a,y_a) b(x_b,y_b)$,记$ \triangle x=| x_a-x_b |$,$ \triangle y=|y_a-y_b |$,那么我们观察网格图,无论怎么移动,$x$坐标都是加减$1$的,同时在加减$1$的过程中我们会发现$y$也会加减$1$,那么,对于不在同一个$x$上,也不在同一个$y$上的点,我们需要

$$\triangle x ,if ~\triangle x>\triangle y$$

$$\triangle x+\frac{\triangle y-\triangle x}{2} ,else$$

这么多步解决问题;而对于$ y$相等的两点,只需$\frac{\triangle y}{2}$即可,对于$x$相等的两点,只需$\triangle x$即可。

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
int dx[]={1,0,-1,1,0,-1};
int dy[]={1,2,1,-1,-2,-1};
const int maxn=10500+5;
pair<int ,int > pt[maxn];
int cnt=0;
inline int myabs(int x){return x<0?-x:x;}
void ini(int k,int sx,int sy)
{
if(k>59) {return ;}
if(k==1){
pt[++cnt].first=0;pt[cnt].second=0;ini(k+1,0,0);
}
else{
sy-=2;
pt[++cnt].first=sx,pt[cnt].second=sy;
for(int i=0;i<k-2;i++) pt[++cnt].first=--sx,pt[cnt].second=--sy;
for(int i=0;i<k-1;i++) pt[++cnt].first=--sx,pt[cnt].second=++sy;
if(k==2)
{
pt[++cnt].first=sx;pt[cnt].second= sy=sy+2;
}else{
pt[++cnt].first=sx;pt[cnt].second= sy=sy+2;
for(int i=0;i<k-2-1;i++) pt[++cnt].first=sx,pt[cnt].second= sy=sy+2;
pt[++cnt].first=sx;pt[cnt].second= sy=sy+2;
}
for(int i=0;i<k-1;i++) pt[++cnt].first=++sx,pt[cnt].second=++sy;
for(int i=0;i<k-1;i++) pt[++cnt].first=++sx,pt[cnt].second=--sy;
if(k==2)
{
pt[++cnt].first=sx;pt[cnt].second= sy=sy-2;
}else{
pt[++cnt].first=sx;pt[cnt].second= sy=sy-2;
for(int i=0;i<k-2-1;i++) pt[++cnt].first=sx,pt[cnt].second= sy=sy-2;
pt[++cnt].first=sx;pt[cnt].second= sy=sy-2;
}
ini(k+1,sx,sy);
}
}
int main()
{
ini(1,0,0);
int a,b;
while(scanf("%d%d",&a,&b)==2)
{
if(a==0 && b==0) break;
if(a==b) printf("The distance between cells %d and %d is 0.\n",a,b);
else{
if(pt[a].first==pt[b].first)
{
printf("The distance between cells %d and %d is %d.\n",a,b,myabs(pt[a].second-pt[b].second)/2);
}else if(pt[a].second==pt[b].second){
printf("The distance between cells %d and %d is %d.\n",a,b,myabs(pt[a].first-pt[b].first));
}else{
int delx=myabs(pt[a].first-pt[b].first),dely=myabs(pt[a].second-pt[b].second);
if(dely>delx) printf("The distance between cells %d and %d is %d.\n",a,b,delx+(dely-delx)/2);
else printf("The distance between cells %d and %d is %d.\n",a,b,delx);
}
}
}
return 0;
}