POJ 3009 Curling 2.0(二)
c
这题的思路很是清晰，因为次数不能大于10，所以递归不会太深，用dfs就可以了，但是在调程序的时候花费了很长时间，幸好是一次就过了。一定要注意变量的变化
[cpp]
#include
#include
#include
int a[40][40];
int stax,stay,endx,endy,step,flag,n,m,resStep;
int vex[]={0,0,-1,1};
int vey[]={-1,1,0,0};
int INF=0x7fffffff;
int main()
{
void dfs(int x,int y);
int i,j,s,t;
while(scanf("%d %d",&m,&n)!=EOF)
{
if(!m&&!n)
{
break;
}
for(i=0;i<=n-1;i++)
{
for(j=0;j<=m-1;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==2)
{
stax=i; stay=j;
}else if(a[i][j]==3)
{
endx=i; endy=j;
}
}
}
step=0;flag=0;resStep=INF;
dfs(stax,stay);
if(flag==0)
{
printf("-1\n");
}else
{
printf("%d\n",resStep);
}
}
return 0;
}
void dfs(int x,int y)
{
int i,j,xend,yend,k,orx,ory;
orx=x; ory=y;
for(i=0;i<=3;i++)
{
step++;
if(step>10)
{
step--;
return ;
}
xend=x+vex[i]; yend=y+vey[i];
if(a[xend][yend]==1)
{
step--;
continue;
}
while(1)
{
xend=x+vex[i]; yend=y+vey[i]; k=0;
if(!(xend>=0&&xend<=n-1)||!(yend>=0& d<=m-1))
{
k=1;
break;
}
if(a[xend][yend]==1||(xend==endx& d==endy))
{
break;
}
x=xend; y=yend;
}
if(k==0)
{
if(xend==endx& d==endy)
{
flag=1;
if(step
{
resStep=step;
}
x=orx; y=ory;
}else
{
a[xend][yend]=0;
dfs(x,y);
a[xend][yend]=1;
x=orx; y=ory;
}
step--;
}else
{
x=orx; y=ory;
step--;
}
}
}