hdu-oj-1242-Rescue

题目链接：Rescue

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>


using namespace std;
//行列及最少时间 
int m, n, res;
//存储区域 
char map[201][201];
//四个方向 
int ds[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

//深度优先搜索算法求取最短时间 
//根据题意，angle的朋友可能有多个，因此可利用反向思维，从angle出发去寻找朋友 
void dfs(int x, int y, int time){
    int i, dx, dy;
    //遍历四个方向 
    for(i = 0; i < 4; i++){
        dx = ds[i][0] + x;
        dy = ds[i][1] + y;
        //确定未超过边界 
        if(dx >= 0 && dx < m && dy >= 0 && dy < n){
            //遇到卫兵时，如果时间加2(1份走到这，一份杀死卫兵)比当前的时间小，则继续搜索 
            if(map[dx][dy] == 'x' && time + 2 < res){
                map[dx][dy] = '#';
                dfs(dx, dy, time+2);
                //搜索完后，设置回原来的状态，方便其他搜索线路进行 ，从而能找到最短时间 
                map[dx][dy] = 'x';
            }
            //遇到路 
            else if(map[dx][dy] == '.' && time + 1 < res){
                map[dx][dy] = '#';
                dfs(dx, dy, time+1);
                map[dx][dy] = '.';
            }
            //遇到朋友 
            else if(map[dx][dy] == 'r'){
                res = (time+1) < res ? time+1:res;
                return ;
            }
        }
    }
}

int main()
{
    int i, j, ix, iy;
    while(scanf("%d%d", &m, &n) != EOF){
        res = 10000;
        getchar();
        for(i = 0; i < m; i++){
            for(j = 0; j < n; j++){
                scanf("%c", &map[i][j]);
                //记录angle的位置 
                if(map[i][j] == 'a'){
                    ix = i;
                    iy = j;
                }
            }
            getchar();
        }
        dfs(ix, iy, 0);
        if(res != 10000)
            printf("%d\n", res);
        else
            printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
    return 0;
}