poj3009 深搜

/*

简单的深搜，需要注意题意里一点，如果一开始就遇到墙壁，则不能往该方向移动

*/

#include<stdio.h>
#include<string.h>
#define MAX 50

int map[MAX][MAX];
int w,h,result;
int start_i,start_j,end_i,end_j;
int d[][2]={ {0,-1}
            ,{-1,0}
            ,{0,1}
            ,{1,0}
            };
void dfs(int i,int j,int step)
{
    int k,next_i,next_j;
    if(step>=result)return;
    step++;
    for(k=0; k<4; ++k)
    {
        next_i = i+d[k][0];
        next_j = j+d[k][1];

        //You may throw it to any direction unless it is blocked immediately
        //如果一开始就是墙壁则不能破开
        if(next_i<0 || next_i>h || next_j<0 || next_j>w || map[next_i][next_j]==1)continue;

        while(next_i>=0 && next_i<h && next_j>=0 && next_j<w && map[next_i][next_j]==0 )
        {
            next_i += d[k][0];
            next_j += d[k][1];
        }
        if(next_i<0 || next_i>=h || next_j<0 || next_j>=w)continue;
        if(map[next_i][next_j]==3)
        {
            if(step<result)result=step;
            return;
        }
        if(map[next_i][next_j]==1)
        {
            map[next_i][next_j]=0;
            dfs(next_i-d[k][0], next_j-d[k][1], step);
            map[next_i][next_j]=1;
        }
    }
}
int main()
{
    int i,j;
    freopen("data","r",stdin);
    while( scanf("%d %d",&w,&h),w!=0 && h!=0 )
    {
        memset(map,0,sizeof(map));
        result = 11;
        for(i=0; i<h; ++i)
        {
            for(j=0; j<w; ++j)
            {
                scanf("%d",&map[i][j]);
                if( map[i][j]==2 )
                {
                    start_i = i;
                    start_j = j;
                    map[i][j]=0;
                }else if( map[i][j]==3 )
                {
                    end_i = i;
                    end_j = j;
                }
            }
        }
        dfs(start_i,start_j,0);
        if(result>10)printf("-1\n");
        else printf("%d\n",result);
    }
    return 0;
}