题目链接:点击打开链接
题目大意:给出一个蜂窝,也就是有六边形组成,从内向外不断的循环(如图)。给出两个数的值u,v按六边形的走法,由中心向六个角走。问由u到v的的最小步数。
首先处理处每个数的坐标,让1点位(0,0)其它的点预先处理出来。
然后计算两个数的距离时,我们能够计算两个数的位置横坐标差位x。纵坐标差位y,当x < y的时候。依照斜线走,走到同样列的时候就能够直接向下走。一直到v,在向下走的时候,一步能够走坐标中的2的距离。
当x>=y的时候,能够先斜线走走到同样的行。然后横正走,一直找到v,在横着走的时候,一次仅仅能走一个坐标。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
struct point{
int x , y ;
}p , q , a[10010] ;
int s[6][2] = { {-1,-1},{-1,1},{0,2},{1,1},{1,-1},{0,-2} } ;
void init() {
a[1].x = a[1].y = 0 ;
int k , i , j , cnt = 1 ;
for(k = 2 ; cnt < 10000 ; k++) {
p.x = a[cnt].x ;
p.y = a[cnt].y-2 ;
a[++cnt] = p ;
for(i = 0 ; i < 6 ; i++) {
for(j = 0 ; j < k-1 ; j++) {
if( i == 0 && j == k-2 ) continue ;
p.x += s[i][0] ;
p.y += s[i][1] ;
a[++cnt] = p ;
if( cnt == 10000 ) break ;
}
if( cnt == 10000 ) break ;
}
}
}
int main() {
init() ;
int u , v , x , y , ans ;
while( scanf("%d %d", &u, &v) && u+v ) {
x = abs(a[u].x-a[v].x) ;
y = abs(a[u].y-a[v].y) ;
ans = 0 ;
if( x < y ) {
ans = x + (y-x)/2 ;
}
else
ans = y + (x-y) ;
printf("The distance between cells %d and %d is %d.\n", u, v, ans ) ;
}
return 0 ;
}