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
孟起 閱讀(1335)
評論(1) 編輯 收藏 引用 所屬分類:
水題