| ||||||||||
| 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 | |||||||||
Re:68行AC代码~~In Reply To:86行AC代码~~ Posted by:xiexinxinlove at 2014-08-05 16:10:23 #include<stdio.h>
#include<cstring>
int x[5]={0,-1,0,1,0},
y[5]={0,0,1,0,-1};
int n,m,i,j,sx,sy,ex,ey,ans;
int p[21][21];
int dfs(int sx,int sy,int ex,int ey,int t)
{
if((sx==ex)&&(sy==ey))
{
if(t-1<ans) ans=t-1;
return 0;
}
if(t>10) return 0;
int dx,dy;
for(int i=1;i<=4;i++)
{
dx=sx+x[i];
dy=sy+y[i];
if(p[dx][dy]==1) continue;
while((p[dx][dy]==0)&&(dx>0)&&(dy>0)&&(dx<=n))
{
if((dx==ex)&&(dy==ey))
{
if(t<ans) ans=t;
return 0;
}
dx+=x[i];
dy+=y[i];
}
if((dx<1)||(dy<1)||(dx>n)||(dy>m)) continue;
p[dx][dy]=0;
dfs(dx-x[i],dy-y[i],ex,ey,t+1);
p[dx][dy]=1;
}
return 0;
}
int main()
{
scanf("%d %d",&m,&n);
while((n!=0)&&(m!=0))
{
memset(p,0,sizeof(p));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%d",&p[i][j]);
if(p[i][j]==2)
{
sx=i;
sy=j;
p[i][j]=0;
}
if(p[i][j]==3)
{
ex=i;
ey=j;
p[i][j]=0;
}
}
ans=1000000;
dfs(sx,sy,ex,ey,1);
if(ans!=1000000) printf("%d\n",ans);
else printf("-1\n");
scanf("%d %d",&m,&n);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator