HDU 1242 Rescue - DFS 回溯

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1242
这题很经典，值得敲上20遍，刚开始题目理解错误，超时
原来有多个friend，
注意dfs判段

/*
HDU 1242 Rescue
http://acm.hdu.edu.cn/showproblem.php?pid=1242
*/
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <cmath>  

const int MAX = 202;  

char map[MAX][MAX];  
bool visit[MAX][MAX];  
int n,m,ax,ay,minx;  

int fangxiang[4][2] = {{-1,0},{0,-1},{1,0},{0,1}} ; // // 4个方向 上 左 下 右

bool isCanReach(int x , int y) // 坐标是否合理
{
    if(x >= 0 && x < n && y >=0 && y < m)
        return true;
    return false;
}

void dfs(int x,int y,int len)
{  
    if(map[x][y] == 'r') // 找到朋友 需要改变最小值
    {  
        if(len < minx)
            minx = len;  
        return;  
    }else{
        if(visit[x][y] || !isCanReach(x,y) || map[x][y] == '#' || len >= minx) // 这里最好加上 len >= minx 判断 ，这样节省时间
            return ;
        visit[x][y] = true;  
        for(int i = 0 ; i < 4 ; i ++)
        {
            int nx = x+fangxiang[i][0];
            int ny = y + fangxiang[i][1];
            if(map[x][y] == 'x')
            {
                dfs(nx,ny,len+2);
            }else{
                dfs(nx,ny,len+1);
            }               
        }
        visit[x][y] = false; // 回溯
    }
}  

int main(){  

    freopen("in.txt","r",stdin);  
    int i,j,len;  
    while(scanf("%d %d%*c",&n,&m)!=EOF)
    {  
        for(i=0;i<n;++i)
        {  
            for(j=0;j<m;++j)
            {  
                visit[i][j] = false;
                map[i][j] = getchar();  
                if(map[i][j]=='a') // 天使的位置
                {  
                    ax = i;  
                    ay = j;  
                }  
            }  
            getchar();  
        }  
        len = 0;  
        minx = INT_MAX;  
        dfs(ax , ay , len);  
        if(minx != INT_MAX){  
            printf("%dn",minx);  
        }else{  
            printf("Poor ANGEL has to stay in the prison all his life.n");  
        }  
    }  
    return 0;  
}

最后

以上就是碧蓝白猫为你收集整理的HDU 1242 Rescue - DFS 回溯的全部内容，希望文章能够帮你解决HDU 1242 Rescue - DFS 回溯所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。