专栏首页calmoundpoj 2251 Dungeon Master(广搜)

poj 2251 Dungeon Master(广搜)

题意:三维空间,可以走上下左右前后六个方向,求最短路径,BFS

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int MAXN=50;

char str[MAXN][MAXN][MAXN];
int step[MAXN][MAXN][MAXN];
int vis[MAXN][MAXN][MAXN];
int l,r,c;
struct Node
{
    int x,y,z;
}s,e;

int BFS()
{
    int i,j;
    Node head,next;
    queue<Node>Q;
    Q.push(s);
    step[s.x][s.y][s.z]=0;
    while(!Q.empty())
    {
        head=Q.front();
        Q.pop();
        for(i=0;i<6;i++)
        {
            next=head;
            if(i==0) next.x-=1;
            if(i==1) next.x+=1;
            if(i==2) next.y-=1;
            if(i==3) next.y+=1;
            if(i==4) next.z-=1;
            if(i==5) next.z+=1;
            if(!vis[next.x][next.y][next.z] && str[next.x][next.y][next.z]==1)
            {
                vis[next.x][next.y][next.z]=1;
                Q.push(next);
                step[next.x][next.y][next.z]=step[head.x][head.y][head.z]+1;
                if(next.x==e.x && next.y==e.y && next.z==e.z) return  step[head.x][head.y][head.z]+1;
            }
        }
    }
    return  0;
}
int main()
{
    int i,j,k;
    while(scanf("%d%d%d",&l,&r,&c)!=EOF)
    {
        if(l==0 && r==0 && c==0) break;
        memset(vis,0,sizeof(vis));
        memset(str,0,sizeof(str));
        for(i=1; i<=l; i++)
        {
            for(j=1; j<=r; j++)
            {
                scanf("%s",str[i][j]+1);
                for(k=1; str[i][j][k]; k++)
                {
                    if(str[i][j][k]=='#') str[i][j][k]=0;
                    if(str[i][j][k]=='.') str[i][j][k]=1;
                    if(str[i][j][k]=='S')
                    {
                        str[i][j][k]=1;
                        s.x=i;
                        s.y=j;
                        s.z=k;
                    }
                    if(str[i][j][k]=='E')
                    {
                        str[i][j][k]=1;
                        e.x=i;
                        e.y=j;
                        e.z=k;
                    }
                }
            }
        }
        int ans=BFS();
        if(ans) printf("Escaped in %d minute(s).\n",ans);
        else printf("Trapped!\n");

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • KMP

    #include<stdio.h> #include<iostream> #include<string.h> using namespace std; vo...

    用户1624346
  • Kindergarten Counting Game

    水题:判断单词有几个  刚开始没仔细想 仅仅判断了空格和空格的个数+1就是单词的个数,后来wa后仔细读读,他说连续的字母是一个单词所以abc!abc这就是两个单...

    用户1624346
  • Catch That Cow

    经过+1,-1,*2的操作,使第一个数等于第二个数 求最少步骤都是用的广搜 #include<stdio.h> #include<queue> #include...

    用户1624346
  • LeetCode 28 Implement strStr()

    实现一个字符串 indexOf()的功能。class Solution { public: int next[100005]; int strStr(st...

    ShenduCC
  • PHP对Json字符串解码返回NULL的一般解决方案

    php对json字符串解码使用json_decode()函数,第一个参数传字符串,第二个参数若为true,返回array;若为false,返回object。如果...

    用户7657330
  • 【Codeforces】1230B - Ania and Minimizing

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    喜欢ctrl的cxk
  • CI(CodeIgniter)框架中URL特殊字符处理与SQL注入隐患分析

    本文实例分析了CI(CodeIgniter)框架中URL特殊字符处理与SQL注入隐患。分享给大家供大家参考,具体如下:

    砸漏
  • PHP中一些可用的方法

    在自然算法中,数字 2 小于数字 10。在计算机排序中,10 小于 2,这是因为 10 中的第一个数字小于 2。

    用户7657330
  • Shell 读取文件 截取字符串

    问天丶天问
  • Kotlin日常编程(一)——拒绝使用"!!"

    这个时候,编译会无法通过,系统会给你改成list.add(str!!)以通过编译。会出现这样的原因是Kotlin有着自己的判空机制。"str!!"表示str一定...

    饮水思源为名

扫码关注云+社区

领取腾讯云代金券