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);也是一样的嘛~
两个相减就是m行的个数了！~ m加个数不就是左边界了嘛~
zb+两倍的行差就是右边界了！~
而且正三角所到的边界是正三角型，反三角所到的边界是反三角型，这点要注意！
posted on 2010-10-06 18:05
孟起 阅读(1305)
评论(1) 编辑 收藏 引用 所属分类:
水题