> step1:
> 一些特殊情况先处理
> 作对称和交换满足 endy >= endx,staty >= statx
> 	if (startx > endx)
> 	{
> 		swap(startx, endx);
> 		swap(starty, endy);
> 	}
> 		if (starty > endy)
> 	{
> 		starty = n - 1 - starty;
> 		endy = n - 1 - endy;
> 	}
> int linecheck(int n) //在某些些直线上预先排除
> {
> 	minsteps = -1;
> 	int disy = endy - starty;
> 	int disx = endx - startx;
> 	if (disx == 0 && disy == 0)
> 		minsteps = 0;
> 	else if ( disy == 2 * disx || disx == 2 * disy)
> 		minsteps = disx < disy ? disx : disy;
> 	else if ( disx + disy == 1 )
> 		minsteps = 3;
> 	else if ( disx == 1 && disy == 1 && ( startx + starty == 0 || endx + endy == 2*(n -1) ) )
> 		minsteps = 4;
> 	else if (disx == 2 && disy == 2)
> 		minsteps = 4;
> 	return minsteps;
> }
> 
> step2:
> 
> 对于 n > 6
> 考虑奇偶性以及马每步跳的步长为3（2+1,1+2）
> 可以得到最小步 step3 >= { (disx + disx) / 3 }
> 
> int Search(int n)
> {
> 	int step2, step3;
> 	int disx = endx - startx;
> 	int disy = endy - starty;
> 
> 	step2 = disy > disx ? disy : disx ;
> 	if (step2 % 2 == 0)
> 		step2 /= 2;
> 	else
> 		step2 = step2 / 2 + 1;
> 
> 	if ( (disx + disy) % 3 == 0 )
> 		step3 = (disx + disy) / 3;
> 	else
> 		step3 = (disx + disy) / 3 + 1;
> 
> 	if (step3 < step2)
> 		step3 = step2;
> 	if ( step3 % 2 != (disx + disy) % 2 )
> 		step3 += 1;
> 	minsteps = step3;
> 	return step3;
> }
> step3
>  对于n < 6 直接用BFS搜索

• Re:强，赞一个，同时bs楼上 (12) xh176233756 2007-01-28 10:43:46