USACO 5.2.1 Snail Trails
中文题目
这题主要是看懂题目的意思,一开始没看懂意思,导致错了两次,后来经过再次再再次的读题,才读懂了题目,题意是:首先选一个方向,然后一直走,如果遇到边界或者障碍物就停下来而且转90度,继续走,但是如果在这之间遇到已经走过的一个地点,那么就之间停止了,主要是后面这个直接停止,如果没看懂就悲剧了.一开始我就是把这看错了.看来还是英语要好好的才行阿.懂了题意之后就直接搜就行了.代码如下:
/
ID:qcx97811
LANG:C
TASK:snail
/
#include
#include
#include
#include
char grid[128][128];
int N,B;
int change_i[4]={-1,0,1,0};
int change_j[4]={0,1,0,-1};
int work(int _i,int _j,int dis)
{
int _x,_y
int tmp_x,tmp_y
int i
int ret,max
max=dis
for(i=0i<4;i++)
{
_x=_i
_y=_j
while(1)
{
_x+=change_i[i];
_y+=change_j[i];
if(2==grid[_x][_y])
{
if(abs(_x-_i)+abs(_y-_j)-1 > 0)
{
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x) & (tmp_y==_y)))
{
grid[tmp_x][tmp_y]=1
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
ret=work(_x-change_i[i],_y-change_j[i],dis+abs(_x-_i)+abs(_y-j)-1);
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x)&(tmp_y==_y)))
{
grid[tmp_x][tmp_y]=0
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
if(max<ret)
max=ret
}
break
}
else
{
if(1==grid[_x][_y])
{
tmp_x=_x
tmp_y=_y
#if 1
ret=dis+abs(_x-_i)+abs(_y-_j)-1
if(ret>max)
max=ret
#endif
break
}
}
}
}
return max
}
int main(void)
{
freopen(“snail.in”,“r”,stdin);
freopen(“snail.out”,“w”,stdout);
int i,j
char ch
int row,ans
scanf(“%d%d%c”,N,&B);
memset(grid,0,sizeof(grid));
for(i=0i<B;i++)
{
scanf(“%c”,ch);
scanf(“%d%c”,row);
grid[row][ch-‘A’+1]=2
}
for(i=0i<=N+1;i++)
grid[0][i]=grid[i][0]=2
for(i=0i<=N+1;i++)
grid[N+1][i]=grid[i][N+1]=2
#if 0
for(i=0;i
{
for(j=0;j
printf(“%d “,grid[i][j]);
printf(“\n”);
}
#endif
grid[1][1]=1
ans = work(1,1,1);
printf(“%d\n“,ans);
return 0
}
ID:qcx97811
LANG:C
TASK:snail
/
#include
#include
#include
#include
char grid[128][128];
int N,B;
int change_i[4]={-1,0,1,0};
int change_j[4]={0,1,0,-1};
int work(int _i,int _j,int dis)
{
int _x,_y
int tmp_x,tmp_y
int i
int ret,max
max=dis
for(i=0i<4;i++)
{
_x=_i
_y=_j
while(1)
{
_x+=change_i[i];
_y+=change_j[i];
if(2==grid[_x][_y])
{
if(abs(_x-_i)+abs(_y-_j)-1 > 0)
{
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x) & (tmp_y==_y)))
{
grid[tmp_x][tmp_y]=1
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
ret=work(_x-change_i[i],_y-change_j[i],dis+abs(_x-_i)+abs(_y-j)-1);
tmp_x=_i+change_i[i];
tmp_y=_j+change_j[i];
while(!((tmp_x==_x)&(tmp_y==_y)))
{
grid[tmp_x][tmp_y]=0
tmp_x+=change_i[i];
tmp_y+=change_j[i];
}
if(max<ret)
max=ret
}
break
}
else
{
if(1==grid[_x][_y])
{
tmp_x=_x
tmp_y=_y
#if 1
ret=dis+abs(_x-_i)+abs(_y-_j)-1
if(ret>max)
max=ret
#endif
break
}
}
}
}
return max
}
int main(void)
{
freopen(“snail.in”,“r”,stdin);
freopen(“snail.out”,“w”,stdout);
int i,j
char ch
int row,ans
scanf(“%d%d%c”,N,&B);
memset(grid,0,sizeof(grid));
for(i=0i<B;i++)
{
scanf(“%c”,ch);
scanf(“%d%c”,row);
grid[row][ch-‘A’+1]=2
}
for(i=0i<=N+1;i++)
grid[0][i]=grid[i][0]=2
for(i=0i<=N+1;i++)
grid[N+1][i]=grid[i][N+1]=2
#if 0
for(i=0;i
{
for(j=0;j
printf(“%d “,grid[i][j]);
printf(“\n”);
}
#endif
grid[1][1]=1
ans = work(1,1,1);
printf(“%d\n“,ans);
return 0
}
