Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用一点数学方法加速 1915

Posted by gemenhao at 2006-05-31 10:47:20 on Problem 1915
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搜索

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator