题意:
给如图中的两个数,求他们之间的最短距离。
思路;
直接模拟,设m<n,先求出这两个数在的层数f1和f2,再求m向左下右下两个方向到n所在行时的对应数字c1,c2,然后判断n是否在c1,c2之间就能求出最短路长度了。
代码:
//poj 2619
//sepNINE
#include <iostream>
#include <cmath>
using namespace std;int main()
{int m,n;scanf("%d%d",&m,&n);if(m>n) swap(n,m); int f1=(int)(ceil(sqrt(m*1.0))+1e-8);int f2=(int)(ceil(sqrt(n*1.0))+1e-8);int df=f2-f1,k=2*f1-1;int c1=m+df*k+df*(df-1);int c2=m+df*k+df*(df+1);int ans=2*(f2-f1);;if(n<=c2&&n>=c1){if(n%2!=c1%2){if((f1%2==0&&m%2==1)||(f1%2==1&&m%2==0)) ++ans;else--ans;}}else{if(n-c2>0)ans+=n-c2;elseans+=c1-n; } printf("%d",ans);
}