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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

诡异的代码!!

Posted by mingruoyuan at 2009-06-26 09:46:09 on Problem 3626
#include<stdio.h>
#include<math.h>
int const maxn=1001;
int head=0,tail=1;
int dis,xi,yi,n,flag=0;
int ii[4]={1,-1,0,0};
int jj[4]={0,0,1,-1};
int f[maxn][maxn]={0};
struct
{
	int step,x,y,dis;
}s[maxn*maxn];
void work(int a,int b)
{
	int i,k,xx,yy;
	if(a==xi&&b==yi)
	{
		printf("%d\n",s[head].step);
		flag=1;
		return;
	}
	for(k=0;k<4;k++)
	{
		xx=a+ii[k];
		yy=b+jj[k];
		if((xx<maxn&&xx>=0)&&(yy>=0&&yy<maxn)&&(f[xx][yy]==0))
		{
			int dd;
			if(xx==xi&&yy==yi)
			{
				printf("%d\n",s[head].step+1);
				flag=1;
				return;
			}
			dd=s[head].dis+abs(xx-xi)+abs(yy-yi);//这里dd可以+1,提交也能过,太诡异了
			for(i=tail;;i--)
				if(s[i-1].dis>dd) s[i]=s[i-1];
				else
				{
					s[i].x=xx;
					s[i].y=yy;
					s[i].step=s[head].step+1;
					s[i].dis=dd;
					f[xx][yy]=1;
					break;
				}
			tail++;
		}
	}
}
int main()
{
	int i,j;
	scanf("%d %d %d",&xi,&yi,&n);
	while(n--)
	{
		scanf("%d%d",&i,&j);
		f[i+500][j+500]=1;
	}
	s[0].x=500;
	s[0].y=500;
	s[0].step=0;
	s[0].dis=abs(xi)+abs(yi);
	xi+=500;
	yi+=500;
	f[500][500]=1;
	for(;;head++)
	{
		work(s[head].x,s[head].y);
		if(flag) break;
	}
	return 0;
}

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