UVa 532 Dungeon Master

📅 2026/7/4 4:29:34 👁️ 次浏览

题目描述题目要求在一个三维迷宫中从起点S出发找到通往终点E的最短路径。迷宫由若干层组成每层有若干行和列。每个单元可以是空地.、岩石#、起点S或终点E。每次移动可以向六个方向北、南、东、西、上、下移动一格耗时111分钟。输出最短时间若无法到达则输出Trapped!。输入格式输入包含多个迷宫。每个迷宫的第一行包含三个整数LLL、RRR、CCC1≤L,R,C≤301 \le L, R, C \le 301≤L,R,C≤30分别表示层数、行数和列数。接下来LLL个块每个块包含RRR行每行CCC个字符。每个块之后有一个空行。输入以0 0 0结束。输出格式对于每个迷宫输出一行若能到达输出Escaped in x minute(s).否则输出Trapped!。样例输入3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0输出Escaped in 11 minute(s). Trapped!题目分析本题的核心是在三维网格中进行广度优先搜索BFS\texttt{BFS}BFS寻找最短路径。BFS\texttt{BFS}BFS实现使用队列存储状态(i,j,k,dist)(i, j, k, dist)(i,j,k,dist)其中(i,j,k)(i, j, k)(i,j,k)为坐标distdistdist为距离。从起点开始向666个方向扩展。遇到障碍#或已访问过则跳过。遇到终点E则输出当前距离。若队列为空仍未找到终点则输出Trapped!。复杂度分析网格大小L×R×C≤27,000L \times R \times C \le 27,000L×R×C≤27,000BFS\texttt{BFS}BFS时间复杂度O(L×R×C)O(L \times R \times C)O(L×R×C)。代码实现// Dungeon Master// UVa ID: 532// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structstate{inti,j,k,minutes;};intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);chargrid[32][32][32],visited[32][32][32];intL,R,C;while(cinLRC,LRC){intstarti,startj,startk,endi,endj,endk;for(inti0;iL;i)for(intj0;jR;j)for(intk0;kC;k){cingrid[i][j][k];if(grid[i][j][k]S)startii,startjj,startkk;if(grid[i][j][k]E)endii,endjj,endkk;}memset(visited,0,sizeof(visited));queuestateunvisited;unvisited.push((state){starti,startj,startk,0});boolescapedfalse;while(!unvisited.empty()){state currentunvisited.front();unvisited.pop();if(current.i0||current.iL||current.j0||current.jR||current.k0||current.kC||grid[current.i][current.j][current.k]#||visited[current.i][current.j][current.k])continue;visited[current.i][current.j][current.k]1;if(current.iendicurrent.jendjcurrent.kendk){coutEscaped in current.minutes minute(s).\n;escapedtrue;break;}unvisited.push((state){current.i-1,current.j,current.k,current.minutes1});unvisited.push((state){current.i1,current.j,current.k,current.minutes1});unvisited.push((state){current.i,current.j-1,current.k,current.minutes1});unvisited.push((state){current.i,current.j1,current.k,current.minutes1});unvisited.push((state){current.i,current.j,current.k-1,current.minutes1});unvisited.push((state){current.i,current.j,current.k1,current.minutes1});}if(!escaped)coutTrapped!\n;}return0;}

相关新闻