hdu1242Rescue（dfs基础）

68 阅读 0 评论 45 点赞

我是靠谱客的博主追寻唇膏，最近开发中收集的这篇文章主要介绍hdu1242Rescue（dfs基础），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：给你一张n*m大小的地图，a是天使，r是士兵，#是墙，x是妖怪，.是路，遇到x要停一秒，问士兵到达天使的最短时间，移动一格也要一秒

思路：这题说是士兵找天使，不如说是天使找士兵，士兵有多个，天使只有一个，当天使能最快找到士兵也符合题意，我直接dfs，方法有点土，不过感觉比bfs好些，当然也牺牲了一些时间，bfs肯定快一些

代码如下：

#include<stdio.h>
#include<string.h>
int book[300][300],n,m,min;
char map[300][300];
int next[4][2]={
    {0,1},{1,0},{0,-1},{-1,0}
};

void dfs(int x,int y,int cnt)
{
    if(map[x][y]=='r')
    {
        if(cnt<min)
            min=cnt;
        return ;
    }
    if(map[x][y]=='x')
        cnt++;
    int i,j,a,b;
    for(i=0;i<=3;i++)
    {
        a=x+next[i][0];
        b=y+next[i][1];
        if(!book[a][b] && map[a][b]!='#' && a>=0 && a<n && b>=0 && b<m)
        {
            book[a][b]=1;
            dfs(a,b,cnt+1);
            book[a][b]=0;
        }
    }
    return ;
}

int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        memset(book,0,sizeof(book));
        min=n*m+1;
        for(i=0;i<n;i++) gets(map[i]);
        for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        if(map[i][j]=='a')
        {
            book[i][j]=1;
            dfs(i,j,0);
            break;
        }
        if(min==n*m+1)
            puts("Poor ANGEL has to stay in the prison all his life.");
        else
            printf("%dn",min);
    }
    return 0;
}