posts - 100,  comments - 15,  trackbacks - 0
//很有趣的一题,让我想起口袋怪兽
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>=10return ;
    
for(dir=0;dir<4;dir++)
    
{
        tx
=x;ty=y;
        
while(1)
        
{
            tx
=tx+dx[dir]; ty=ty+dy[dir];
            
if(tx<0 || tx>=|| 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!=|| 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 阅读(987) 评论(10)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理