rescue_hdu_1242

换了好几次思路,终于~
这道题做要用逆向思维,从a找r,深搜即可,广搜会有bug

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int walk[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int walked[210][210],min=99999,flag;
char map[210][210];
void dfs(int x,int y,int step){
    int i;
    if(map[y][x]=='r'){
        flag=1;
        if(step<min){
            min=step;
        }
        return;
    }
    for(i=0;i<4;i++){
        int tempx=x+walk[i][0],tempy=y+walk[i][1];
        if(map[tempy][tempx]=='.'&&walked[tempy][tempx]==0){
            walked[tempy][tempx]=1;
            dfs(tempx, tempy, step+1);
            walked[tempy][tempx]=0;
        }
        if(map[tempy][tempx]=='x'&&walked[tempy][tempx]==0){
            walked[tempy][tempx]=1;
            dfs(tempx, tempy, step+2);
            walked[tempy][tempx]=0;
        }
        if(map[tempy][tempx]=='r'){
            dfs(tempx, tempy, step+1);
        }
    }
    return;
}
int main() {
    int n,m,i,j;
    while(~scanf("%d%d",&n,&m)){
        getchar();
        int sx,sy;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                scanf("%c",&map[i][j]);
                if(map[i][j]=='a'){
                    sx=j;
                    sy=i;
                    walked[i][j]=1;
                }
            }
            getchar();
        }
        dfs(sx, sy, 0);
        if(flag==0){
            printf("Poor ANGEL has to stay in the prison all his life.n");
        }
        else{
            printf("%dn",min);
        }
        memset(map, 0, sizeof(map));
        memset(walked, 0, sizeof(walked));
        flag=0;
        min=99999;
    }
    return 0;
}