这道题也是一道很基础的bfs,仅仅是图从二维变成三维
在入队列之前进行判断比出队列之后再进行判断会节约运行的时间,因为减少了入队、出队的赋值操作,对于bfs这样低效的算法,在某些题目里面是很容易超时的,所以能够节约点时间还是好的
还有一点就是自己手写的队列要比调用STL的队列要快一些,但是提高了编程复杂度
#include<iostream> #include<cstring> #include<queue> #define MAXN 30+10 using namespace std; struct Point { int x,y,z,step; }; char mat[MAXN][MAXN][MAXN]; char vis[MAXN][MAXN][MAXN]; int bfs(Point start) { vis[start.z][start.x][start.y]=1; queue<Point> q; q.push(start); while(!q.empty()) { Point cur=q.front(); q.pop(); int dir[8][3]={-1,0,0,1,0,0,0,-1,0,0,1,0,0,0,-1,0,0,1}; for(int i=0;i<8;i++) { Point next; next.z=cur.z+dir[i][0]; next.x=cur.x+dir[i][1]; next.y=cur.y+dir[i][2]; next.step=cur.step+1; if(!vis[next.z][next.x][next.y]&&mat[next.z][next.x][next.y]!='#') { if(mat[next.z][next.x][next.y]=='E') return next.step; vis[next.z][next.x][next.y]=1; q.push(next); } } } return -1;//-1代表无法到达 } void init()//初始化,全部设为墙壁 { memset(vis,0,sizeof(vis)); for(int i=0;i<MAXN;i++) for(int j=0;j<MAXN;j++) for(int k=0;k<MAXN;k++) mat[i][j][k]='#'; } int main() { int L,R,C; Point start; while(cin>>L>>R>>C&&L&&R&&C) { init(); for(int i=1;i<=L;i++)//之所以从1开始,是因为外面增加一层墙壁可以省去越界的判断 for(int j=1;j<=R;j++) for(int k=1;k<=C;k++) { cin>>mat[i][j][k]; if(mat[i][j][k]=='S') { start.z=i; start.x=j; start.y=k; start.step=0; } } int ans=bfs(start); if(ans==-1) cout<<"Trapped!"<<endl; else cout<<"Escaped in "<<ans<<" minute(s)."<<endl; } return 0; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 901题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 811题目:http://uva.onlinejudge.org/i ... -
UVa 216 Getting in Line
2012-08-29 20:48 724题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1640题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1049题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 874题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 696题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 659题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 763题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 604题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1126题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 879题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 658题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 874题目:http://uva.onlinejudge.org/i ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 825题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 745题目:http://uva.onlinejudge.org/i ...
相关推荐
uva532 Dungeon Master的源代码,并且AC了
北大POJ2251-Dungeon Master 解题报告+AC代码
C++题目
Dungeon Master's Vault是一个Web服务器,允许您托管自己的D&D 5th Edition角色生成器网站。 入门 要运行自己的Dungeon Master's Vault安装,有两种方法可以执行。 从我们的Docker存储库中提取Docker容器。 建立...
Dungeon Master Nintendo DS端口(用于在NDS上播放DM,CSB和DM2)
••••积分•隐私•许可 关于您是否在Roll20上玩D&D,但更喜欢使用Dungeon Master's Vault管理角色? VTT Bridge将您的Dungeon Master的Vault角色表无缝连接到Roll20游戏。 主要特征滚动能力检查,武器攻击...
地牢大师 从此处运行DungeonMaster机器人的地方
来自FTL / Interplay的经典游戏Dungeon Master的免费实现,适用于GNU / Linux + SDL。 进一步的实现:SDL库支持的其他(首选POSIX)系统。
JDMG 像游戏一样的Dungeon Master的Javascript 此源代码基于Joe Shaw创建的DMJ。 ( )
DUNGEON-MASTER-WEBGL
github_dungeon_master
Java应用程序,旨在在针对PDA的AD&D游戏会话中帮助地牢主
DM Ruler帮助地下城主创建规则,senario,世界,地图,怪物数据库,咒语数据库等。 一切都可以使用xml文件进行自定义。 构建您自己的系统或使用现有的系统。
减轻地牢大师生活的全套工具
地牢大师 生成巨大而复杂的地牢迷宫世界,难度逐渐增加,并且会出现敌对的小头目。 贡献者 希尔本 执照 根据。
Dungeon Masters备忘单是一个系统,允许您输入有关Dungeons and Dragons 3.5任务或遭遇的重要信息,包括玩家角色,NPC,怪物,笔记,主动命令计算器和随机骰子。
CPS_DUNGEON_MASTER_PROJECT
单击“ Dungeon Master.exe”。 享受。 :) 使用项目 下载“ Project src”目录或克隆。 在Unity中,使用选项打开项目。 用作主文件夹“ Project src”目录。 现在您已经准备好,在“资产”中查找场景。 游戏机 ...
Dungeon Architect unity地图制作插件,很好用的插件,帮助你快速制作地图
该程序旨在帮助Dungeon大师管理NPC的统计信息。 该程序目前仅在Windows上可用,并且可以与以下语言一起很好地进行编译:VS2010,VS2008,Sharpdev和MonoDevelop(仅.net编译。与mono版本不兼容)。该应用程序具有很...