大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 17007 | Accepted: 6620 |
Description
Is an escape possible?
If yes, how long will it take?
Input
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘#’ and empty cells are represented by a ‘.’. Your starting position is indicated by ‘S’ and the exit by the letter ‘E’. There’s a single blank line after each level. Input is terminated by three zeroes for L, R and C.
Output
Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
3维地图给起点和终点搜最短路。。刷dfs专题刷出来这玩意也是醉了。。
BFS暴搜
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define ll long long #define maxn 360 #define pp pair<int,int> #define INF 0x3f3f3f3f #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; int n,m,sx,sy,sz,A,B,C; bool vis[105][105][105]; char ma[105][105][105]; struct node { int x,y,z,step; }; int mv[6][3]={{0,0,1},{0,0,-1},{1,0,0},{-1,0,0},{0,1,0},{0,-1,0}}; void bfs() { queue <node> Q; node t; t.x=sx;t.y=sy;t.z=sz;t.step=0; vis[sx][sy][sz]=1; Q.push(t); while(!Q.empty()) { node f=Q.front();Q.pop(); if(ma[f.x][f.y][f.z]=='E') { printf("Escaped in %d minute(s).\n",f.step); return ; } for(int i=0;i<6;i++) { t.x=f.x+mv[i][0]; t.y=f.y+mv[i][1]; t.z=f.z+mv[i][2]; if(0<=t.x&&t.x<A&&0<=t.y&&t.y<B&&0<=t.z&&t.z<C&&!vis[t.x][t.y][t.z]&&ma[t.x][t.y][t.z]!='#') { vis[t.x][t.y][t.z]=1; t.step=f.step+1; Q.push(t); } } } puts("Trapped!"); } int main() { while(scanf("%d%d%d",&A,&B,&C)!=EOF) { if(!A&&!B&&!C)break; memset(vis,0,sizeof(vis)); for(int i=0;i<A;i++) for(int j=0;j<B;j++) scanf("%s",ma[i][j]); for(int i=0;i<A;i++) for(int j=0;j<B;j++) for(int k=0;k<C;k++) if(ma[i][j][k]=='S') { sx=i;sy=j;sz=k; break; } bfs(); } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116741.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...