| ||||||||||
| 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 | |||||||||
感觉对dfs有更多的理解了1AC#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;
const int MAX=22;
int map[MAX][MAX];
int n,m;
int x1,y1,x2,y2;
int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};
int flag=0;
int step;
struct node
{
int x,y;
}a;
bool move(int x,int y,int i)
{
a.x=x,a.y=y;
if(map[x][y]==3)
{
flag=1;
a.x=x,a.y=y;
return true;
}
if(x<1||x>n||y<1||y>m)
return false;
if(map[x][y]!=0)
return false;
while(1)
{
x+=fx[i];
y+=fy[i];
if(x<1||x>n||y<1||y>m)
return false;
if(map[x][y]==3)
{
flag=1;
a.x=x,a.y=y;
return true;
}
if(map[x][y]!=0)
{
return true;
}
a.x=x,a.y=y;
}
}
void dfs(int x,int y,int ans)
{
if(ans>10)
{
return ;
}
if(flag)
{
step=min(step,ans);
return ;
}
for(int i=0;i<4;++i)
{
int tx=x+fx[i];
int ty=y+fy[i];
if(move(tx,ty,i)==false)
continue;
else
{
tx=a.x,ty=a.y;
if(flag)
{
// printf("%d %d\n",step,ans);
step=min(step,ans);
return ;
}
map[tx+fx[i]][ty+fy[i]]=0;
// for(int k=1;k<=n;++k)
// {
// for(int j=1;j<=m;++j)
// printf("%2d",map[k][j]);
// printf("\n");
// }
dfs(tx,ty,ans+1);
map[tx+fx[i]][ty+fy[i]]=1;
flag=0;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
if(m==0&&n==0)
break;
step=INF;
flag=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&map[i][j]);
if(map[i][j]==2)
{
x1=i,y1=j;
map[i][j]=0;
}
if(map[i][j]==3)
{
x2=i,y2=j;
}
}
}
dfs(x1,y1,0);
if(step!=INF&&step<=9)
printf("%d\n",step+1);
else
printf("-1\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