题意：求在如下的图中的一个数字到另一个数字穿越的最少边数。

Analyse:

若m，n在同一行上，则step=|m-n|；若不在同一行，先确保m<n。然后讨论：1.m所在的三角形向下，第一步必定先向左（或向右）移动，再向下移动；2.m所在的三角形向上，第一步必定向下移动，然后再向左（或向右）移动。因此第一步先研究m所在三角形的位置和方向，若向下则先向左（或向右）移动一步。后面的移动都以m所在三角形向上为基础。若有移动，先设step=1，否则step=0。

设行距为d，列距为hd；

若行距与列距相等，则step=step+d*2;

若行距小于列距，则step=step+2*d+hd-d；

若行距大于列距且n所在三角形向上，则step=step+2*hd+((d-hd)/2)*4；

若行距大于列距且n所在三角形向下，则step=step+2*hd+((d-hd)/2)*4+1；

 

1 #include
       
          2 #include
        
           3 //以下函数由m的值判断出m所在的行，m位置在所在行的序数，该行序号，该行的中间三角形的序数  4 void locate(int n,int *mid,int *thisn,int *row)  5 {
      6     *row =(int) ceil(sqrt(n));  7     *mid = *row;  8     *thisn = n-(*row-1)*(*row-1);  9 } 10 int horizon(int m,int mid1,int thisn1,int n,int mid2,int thisn2) 11 {
     12     //本函数的操作都以m所在三角形向上为基础 13 //    printf("m=%d,thisn1=%d,mid1=%d,thisn2=%d,mid2=%d\n",m,thisn1,mid1,thisn2,mid2); 14     if( (thisn1-mid1)*(thisn2-mid2)<0 )//n,m分布在中轴两侧 15         return abs(thisn1-mid1)+abs(thisn2-mid2); 16     else 17         return abs( abs(thisn1-mid1)-abs(thisn2-mid2) ); 18 } 19 main() 20 {
     21     int n,m,temp; 22     int mid1,thisn1,row1,mid2,thisn2,row2; 23     int d,step,hd;//d储存行距,step储存穿越的边数,hd储存m与n之间水平距离 24     while(scanf("%d%d",&m,&n)==2) 25     {
     26         if(m>n) 27         {
     28             temp=n; 29             n=m; 30             m=temp; 31         } 32         locate(m,&mid1,&thisn1,&row1); 33         locate(n,&mid2,&thisn2,&row2); 34         d=row2-row1; 35 //        printf("d=%d,hd=%d\n",d,horizon(m,mid1,thisn1,n,mid2,thisn2) ); 36         if(d==0) 37             step=thisn2-thisn1; 38         else 39         {
     40             step=0; 41             if(row1%2-m%2!=0)//m所在的三角形向下 42             {
     43                 //m先右移一个三角形 44                 if( horizon(m-1,mid1,thisn1-1,n,mid2,thisn2)>=horizon(m+1,mid1,thisn1+1,n,mid2,thisn2) ) 45                 {
     46                     m++; 47                     thisn1++; 48                 } 49                 //m先左移一个三角形 50                 else 51                 {
     52                     m--; 53                     thisn1--; 54                 } 55                 step=1; 56             } 57             hd=horizon(m,mid1,thisn1,n,mid2,thisn2); 58             //以下操作都以m所在三角形向上为基础 59             if(hd>=d)//若列距大于等于行距 60                 step+=hd+d; 61             else 62             {
     63                 d-=hd;//先到与n同列数的三角形，到了一个向上的三角形 64                 step+=2*hd; 65                 step+=4*(d/2); 66                 if(n%2-row2%2!=0)//n所在的三角形向下 67                     step++; 68             }    69         } 70         printf("%d\n",step); 71     } 72 }
        
       

大量的注释方便程序的调试。