学步园

http://poj.org/problem?id=3009

其实一开始就想把dir当作参数，根据map条件搜索，但是却是在递归中用while处理的，处理不好map由0变1的回溯.

蛋疼的代码，看着就纠结。。

code:

#include<cstdio>
#include<cstring>
#define Min(a, b)   a>b?b:a
#define MAX 1e+6
int tur[4][2] = {0, 1, 0, -1, 1, 0, -1, 0} ;
int map[21][21] ;
int w, h, ans, sx, sy, ex, ey ;
bool check(int x, int y){
    if(x<0||x>=w||y<0||y>=h)    return false ;
    return true ;
}
void dfs(int x, int y, int dir, int count){
    int tx = x + tur[dir][0] ;
    int ty = y + tur[dir][1] ;
    if(!check(tx, ty)||count>10)
        return ;
    if(map[tx][ty]==1){
        map[tx][ty] = 0 ;
        for(int i=0; i<4; i++){
            if(map[x+tur[i][0]][y+tur[i][1]]==1||!check(x+tur[i][0], y+tur[i][1]))  continue ;
            dfs(x, y, i, count+1) ;
        }
        map[tx][ty] = 1 ;
    }
    else if(map[tx][ty]==3){
        ans = Min(ans, count) ;
        return ;
    }else{
        dfs(tx, ty, dir, count) ;
    }
}
int main(){
    int i, j ;
    while(~scanf("%d%d", &w, &h)&&w+h){
        for(i=0; i<h; i++)
            for(j=0; j<w; j++){
                scanf("%d", &map[j][i]) ;
                if(map[j][i]==2)    sx = j, sy = i ;
                else if(map[j][i]==3)    ex = j, ey = i ;
            }
        ans = MAX ;
        for(i=0; i<4; i++){
            if(map[sx+tur[i][0]][sy+tur[i][1]]==1||!check(sx+tur[i][0], sy+tur[i][1]))  continue ;
            dfs(sx, sy, i, 1) ;
        }
        if(ans==MAX)    printf("-1\n") ;
        else    printf("%d\n", ans) ;
    }
    return 0 ;}