文档章节

POJ -- 2251 Dungeon Master

傅芃芃
 傅芃芃
发布于 2016/03/11 11:20
字数 713
阅读 22
收藏 0

题目网址:POJ -- 2251

很典型的宽度优先搜索,尽管是一个三维的图,方法还是一模一样。 队列放入入口坐标,从入口坐标不断向外一层一层拓展,拓展到的元素进入队列并且标记该元素到入口的距离。

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 50;
int L, R, C;
int Sz, Sx, Sy;
int Ez, Ex, Ey;
char maze[maxn][maxn][maxn];
int dist[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
queue<int> q;
int bfs()
{
    while(!q.empty()) q.pop();
    q.push(Sz); q.push(Sx); q.push(Sy);
    dist[Sz][Sx][Sy] = 0;
    vis[Sz][Sx][Sy] = 1;        /// 表示已在队列中
    while(!q.empty())
    {
        int z = q.front(); q.pop();
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();

        if(z == Ez && x == Ex && y == Ey) return dist[z][x][y];

        if(z + 1 <= L && maze[z+1][x][y] != '#' && !vis[z+1][x][y])
        {
            q.push(z+1); q.push(x); q.push(y);
            dist[z+1][x][y] = dist[z][x][y] + 1;
            vis[z+1][x][y] = 1;
        }
        if(z - 1 >= 1 && maze[z-1][x][y] != '#' && !vis[z-1][x][y])
        {
            q.push(z-1); q.push(x); q.push(y);
            dist[z-1][x][y] = dist[z][x][y] + 1;
            vis[z-1][x][y] = 1;
        }
        if(x + 1 <= R && maze[z][x+1][y] != '#' && !vis[z][x+1][y])
        {
            q.push(z); q.push(x+1); q.push(y);
            dist[z][x+1][y] = dist[z][x][y] + 1;
            vis[z][x+1][y] = 1;
        }
        if(x - 1 >= 1 && maze[z][x-1][y] != '#' && !vis[z][x-1][y])
        {
            q.push(z); q.push(x-1); q.push(y);
            dist[z][x-1][y] = dist[z][x][y] + 1;
            vis[z][x-1][y] = 1;
        }
        if(y + 1 <= C && maze[z][x][y+1] != '#' && !vis[z][x][y+1])
        {
            q.push(z); q.push(x); q.push(y+1);
            dist[z][x][y+1] = dist[z][x][y] + 1;
            vis[z][x][y+1] = 1;
        }
        if(y - 1 >= 1 && maze[z][x][y-1] != '#' && !vis[z][x][y-1])
        {
            q.push(z); q.push(x); q.push(y-1);
            dist[z][x][y-1] = dist[z][x][y] + 1;
            vis[z][x][y-1] = 1;
        }
    }
    return 0;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(scanf("%d%d%d", &L, &R, &C) && L)
    {
        memset(dist, 0, sizeof(dist));
        memset(vis, 0, sizeof(vis));

        for(int i = 1; i <= L; i++)
        for(int j = 1; j <= R; j++) {
            scanf("%s", &maze[i][j][1]);
        }
        for(int i = 1; i <= L; i++)
        for(int j = 1; j <= R; j++)
        for(int k = 1; k <= C; k++)
            if(maze[i][j][k] == 'S') { Sz = i; Sx = j; Sy = k; }
            else if(maze[i][j][k] == 'E') { Ez = i; Ex = j; Ey = k; }

        int dist = bfs();
        if(dist) printf("Escaped in %d minute(s).\n", dist);
        else printf("Trapped!\n");
    }
    return 0;
}

代码写得比较繁琐,bfs()中当前元素的相邻元素入队列的判定是一个一个手打上去的,其实可以构建一个数组d[][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}}; 这样把相邻坐标的计算写在循环中会更不宜出错。

一开始将g[][][]声明成了int型。。。犯过好几次这种错误了。存储图的原输入的时候一定记得用char型数组存储。

© 著作权归作者所有

傅芃芃
粉丝 14
博文 21
码字总数 19341
作品 0
私信 提问
【POJ - 2251】Dungeon Master (bfs+优先队列)

Dungeon Master Descriptions: You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with roc......

Sky丨Star
06/02
0
0
POJ 2251 Dungeon Master

Dungeon Master   You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It tak......

suvvm
2018/12/06
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
160
1
spark shell 运行异常

Association with remote system [akka.tcp://sparkMaster@master :7077] has failed, address is now gated for [5000] ms. Reason: [Association failed with [akka.tcp://sparkMaster@mas......

知行合一1
2016/08/26
496
2

没有更多内容

加载失败,请刷新页面

加载更多

全球第一时间响应:Rancher发布2.3.1,支持K8S CVE修复版本

北京时间2019年10月17日,Kubernetes发布了新的补丁版本,修复了新近发现的两个安全漏洞:CVE-2019-11253和CVE-2019-16276。Rancher第一时间响应,就在当天紧随其后发布了Rancher v2.3.1和R...

RancherLabs
17分钟前
3
0
EMQ X 规则引擎系列 (八)桥接消息到 MQTT Broker

桥接概念 桥接是一种连接多个 EMQ X 或者其他 MQTT 消息中间件的方式。不同于集群,工作在桥接模式下的节点之间不会复制主题树和路由表。桥接模式所做的是: 按照规则把消息转发至桥接节点;...

EMQX
20分钟前
4
0
《2019年上半年云上企业安全指南》详解安全建设最易忽视的问题!

《2019年上半年云上企业安全指南》是阿里云基于对云安全中心监测到的威胁情报进行分析,形成的一份云上企业安全建设指南。通过对云上企业安全建设现状及多维度威胁情报的分析,得出企业安全建...

开源中国小二
21分钟前
3
0
一天之际在于晨之KMP算法

(我觉得不需要明白原理,应该是在面试或者工作的时候,该想到用什么算法以及之后直接赋值我这里的代码就好了) 下面的情况我们第一时间考虑想到的是用KMP算法。 情况一:// ts字符串是否包...

木九天
24分钟前
3
0
如何通过反射机制创建对象?

1. 什么是反射? Java 反射机制在程序运行时,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性。这种动态的获取信息以及动态调用对...

happywe
24分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部