【题解-信息学奥赛一本通】1248：Dungeon Master

题目1248Dungeon Master题目描述这题是一个三维的迷宫题目其中用‘.’表示空地‘#’表示障碍物‘S’表示起点‘E’表示终点求从起点到终点的最小移动次数解法和二维的类似只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动每次都只能移到相邻的空位每次需要花费一分钟求从起点到终点最少要多久。输入多组测试数据。一组测试测试数据表示一个三维迷宫前三个数分别表示层数、一个面的长和宽后面是每层的平面图。前三个数据为三个零表示结束。输出最小移动次数。时空限制1s / 64MB样例输入3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0样例输出Escaped in 11 minute(s). Trapped!提示对于题目给出数据的含义就是输入lrc分别代表迷宫有l层每层长宽分别是cr。对于数据以可以这样移动:(1,1,1)-(1,1,2)-(1,1,3)-(1,1,4)-(1,1,5)-(1,2,5)-(1,3,5)-(1,3,4)-(1,4,4)-(2,4,4)-(2,4,5)-(3,4,5)共11步就可以到达终点 对于数据二明显不能到达则输出Trapped这题用BFS解每次去队首元素如果是终点则输出结果移动的次数否则从该点开始分别向东南西北上下移动如果可以走的话并继续搜如果到队列为空还没搜到解法则说明无解。代码#includebits/stdc.husingnamespacestd;constintN10010;inth,n,m,sx,sy,sz,ex,ey,ez;charg[N][N][N];intdis[N][N][N];intdx[10]{-1,1,0,0,0,0},dy[10]{0,0,-1,1,0,0},dz[10]{0,0,0,0,1,-1};structnode{intx,y,z;};voidbfs(intx1,inty1,intz1){queuenodeq;q.push({x1,y1,z1});dis[x1][y1][z1]0;while(!q.empty()){node tq.front();q.pop();for(inti0;i6;i){intxxt.xdx[i],yyt.ydy[i],zzt.zdz[i];if(xx1||xxn||yy1||yym||zz1||zzh)continue;if(g[xx][yy][zz]#)continue;if(dis[xx][yy][zz]-1){q.push({xx,yy,zz});dis[xx][yy][zz]dis[t.x][t.y][t.z]1;if(xxexyyeyzzez)return;}}}}intmain(){while(cinhnm,h||n||m){for(intk1;kh;k)for(inti1;in;i)for(intj1;jm;j){cing[i][j][k];if(g[i][j][k]S)sxi,syj,szk;if(g[i][j][k]E)exi,eyj,ezk;dis[i][j][k]-1;}bfs(sx,sy,sz);if(dis[ex][ey][ez]-1)coutEscaped in dis[ex][ey][ez] minute(s).endl;elseputs(Trapped!);}return0;}结果