HDU 1242 Rescue (DFS)

清疚 2022-06-08 08:42 75阅读 0赞

//题意自己看，不会度娘

#include <stdio.h>
    #include <math.h>
    #include <string.h>
    char map[205][205];//地图
    int flag[205][205];//标记
    int n,m,ok,num;
    void DFS(int x,int y,int step)
    {
        if(flag[x][y]||map[x][y]=='#'||step>=num)//剪枝。如果走到墙或者步数不是最少还有这个坐标已经走过
        return;
        if(map[x][y]=='r')//表示已经营救成功
        {
            ok=1;
            if(step<num)
            num=step;
            return;
        }
        if(map[x][y]=='x')//如果是警卫，步数加一
        step++;
        flag[x][y]=1;//将flag[x][y]标记为1表示已走
        DFS(x+1,y,step+1);
        DFS(x-1,y,step+1);
        DFS(x,y+1,step+1);
        DFS(x,y-1,step+1);//四个方向一一走过，可以继续走的话就继续往下走
        flag[x][y]=0;//如果运行到这里说明四个方向都不行，将flag[x][y]重新标记为未走
    } 
    int main(int argc, char *argv[])
    {
    while(~scanf("%d %d%*c",&n,&m))
    {
        int si,sj,i,j;
        memset(map,'#',sizeof(map));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%c",&map[i][j]);
                if(map[i][j]=='a')
                {
                    si=i;
                    sj=j;
                }//标记位置
            }
            getchar();
        }
    ok=0;
    num=100000;
    DFS(si,sj,0);
    if(ok)
    printf("%d\n",num);
    else
    printf("Poor ANGEL has to stay in the prison all his life.\n");    
    }
        return 0;
    }

//Start-ZJ

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关【杭电oj1242】Rescue

![这里写图片描述][20160729230431627] ![这里写图片描述][20160729230445951] 在下是菜鸡，一个细节没注意到，非void函数是要有

梦里梦外;/ 2022年09月24日 11:24/ 0 赞/ 161 阅读

相关 HDU 1242(bfs)

题意：一个朋友拯救angel，'a' 是angel， 'x'是士兵， 'r'是朋友，'\'是墙壁。没走一步花费一个单位的时间，遇到士兵与士兵搏斗花费一个单位的时间，求最短时间。

偏执的太偏执、/ 2022年09月20日 11:29/ 0 赞/ 71 阅读

相关杭电1242-Rescue（bfs+优先队列||队列）

Rescue Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

àì夳堔傛蜴生んèń/ 2022年08月04日 12:00/ 0 赞/ 122 阅读

相关 HDU-1242 Rescue BFS+优先队列

题目链接：https://vjudge.net/contest/176287\problem/B "."代表路 "\"代表墙 "a"代表angel "r"代表起点 "

淩亂°似流年/ 2022年06月10日 03:38/ 0 赞/ 128 阅读

相关 HDU 3717 Rescue（二分+技巧性模拟）【详解】

The princess is trapped in a magic place. In this place, there are N magic stones. In or

电玩女神/ 2022年06月09日 08:26/ 0 赞/ 96 阅读

相关 HDU 1242 Rescue (DFS)

//题意自己看，不会度娘 include <stdio.h> include <math.h> include <string.h>

清疚/ 2022年06月08日 08:42/ 0 赞/ 76 阅读

相关 Rescue-HDU-深搜

Rescue Problem Description Angel was caught by the MOLIGPY! He was put in pri

╰半橙微兮°/ 2022年06月05日 06:26/ 0 赞/ 162 阅读

相关 HDU - 1242 Rescue (BFS)

Rescue Problem Description Angel

怼烎@/ 2022年05月19日 02:07/ 0 赞/ 81 阅读

相关 HDU 1241 Rescue ——————BFS , 优先队列

Rescue Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Other

约定不等于承诺〃/ 2022年05月14日 11:29/ 0 赞/ 127 阅读

相关 HDU 1242 Rescue

原题目链接[HDU1242][] -------------------- 分类 HDU 搜索 BFS 优先队列 --------------------

怼烎@/ 2022年04月16日 04:59/ 0 赞/ 81 阅读