//很有趣的一題，讓我想起口袋怪獸
WA了老半天，原來是兩個if()放反了，居然不判RE判WA，o(╯□╰)o
#include<iostream>
using namespace std;
char map[21][21];
int dx[4]=
{0,-1,0,1};
int dy[4]={-1,0,1,0};
int h,w,sx,sy;
int step;
int res;
void dfs(int x,int y)
{
int dir,tx,ty;
if(step>=10) return ;
for(dir=0;dir<4;dir++)
{
tx=x;ty=y;
while(1)
{
tx=tx+dx[dir]; ty=ty+dy[dir];
if(tx<0 || tx>=h || ty<0 || ty>=w )break;
if(map[tx][ty]=='3')
{
step++;
//printf("--%d--\n",step);
if(res>step) res=step;
step--;
return ;
}
else
if(map[tx][ty]=='1')
{
tx=tx-dx[dir];ty=ty-dy[dir];
if(tx!=x || ty!=y)
{
map[tx+dx[dir]][ty+dy[dir]]='0';
step++;
dfs(tx,ty);
step--;
map[tx+dx[dir]][ty+dy[dir]]='1';
}
break;
}
}//while
}//for
}//dfs
int main()
{
int i,j;
while(scanf("%d%d",&w,&h)!=EOF && w)
{
step=0;
for(i=0;i<h;i++)
for(j=0;j<w;j++)
scanf(" %c",&map[i][j]);
for(i=0;i<h;i++)
for(j=0;j<w;j++)
if(map[i][j]=='2') {sx=i;sy=j;break;}
res=9999999;
dfs(sx,sy);
if(res>10) printf("-1\n");
else printf("%d\n",res);
}
return 0;
}
posted on 2009-07-22 23:46
wyiu 閱讀(1009)
評論(10) 編輯 收藏 引用 所屬分類:
POJ