| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
诡异的代码!!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator