A triangle field is numbered with successive integers in the way shown on the picture below.

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller's route.

Write the program to determine the length of the shortest route connecting cells with numbers N and M.
#include <stdio.h>
#include
<math.h>
int main()
{

int temp,n,m,s,flag=3,cn,cm,zb,yb,cc,k,sj;

while(scanf("%d%d",&m,&n)==2 )

{
flag
=3;  s=0;  k=0;

if(m>n)

{
temp
=m;  m=n;  n=temp;
}

cn
=(int)ceil(sqrt(n));    //判断n和m所在层数
cm=(int)ceil(sqrt(m));
cc
=abs(cn-cm);        //判断两点层差
zb=m+(cn-1)*(cn-1)-(cm-1)*(cm-1);  //判断m辐射到n层所及范围的左边界和右边界
yb=zb+2*cc;

if(n>=zb && n <=yb) //判断n在m范围所须步数
{
s
=2*(cc);
k
=1;
}

else

{

if(n<zb)   //判断n到m边界及m点所须步数和
s=2*(cc)+abs(n-zb);

else
s
=2*(cc)+abs(n-yb);
}

sj
=m-(cm-1)*(cm-1);   //判断三角类型0正,1倒
if(abs(n-m)% 2 !=(cc) % 2)

{

if(sj % 2 ==1 )
flag
=1;

else
flag
=0;
}

if(flag==1 && k==1)
s
=s-1;      //假如n点在m点辐射范围内,正三角-1,倒三角+1,不在不判断.
if(flag==0 && k==1
s
=s+1;
printf(
"%d\n",s);
}

return 0;
}
cn-1)*(cn-1)是1到n-1行末尾的数，也就是1-n的里面小三角形的个数~，
(cm-1)*(cm-1);也是一样的嘛~

zb+两倍的行差就是右边界了！~

posted on 2010-10-06 18:05 孟起 阅读(1276) 评论(1)  编辑 收藏 引用 所属分类: 水题

# re: HDU1030 Delta-wave 找规律 2010-11-11 15:23 | gdut

 只有注册用户登录后才能发表评论。 【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！ 相关文章: