合肥 做网站的,吉林市一建公司官网,车辆租赁的网站建设,建立网站的服务器题目#xff1a;
你被困在一个3D地牢中且继续寻找最短路径逃生#xff01;地牢由立方体单位构成#xff0c;立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且迷宫四周坚石环绕。
是否存在逃出生天的可能性#xff1f;如果存在#…题目
你被困在一个3D地牢中且继续寻找最短路径逃生地牢由立方体单位构成立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且迷宫四周坚石环绕。
是否存在逃出生天的可能性如果存在则需要多少时间 Input - 输入 输入第一行是一个数表示地牢的数量。 每个地牢的描述的第一行为LR和C皆不超过30。 L表示地牢的层数。 R和C分别表示每层地牢的行与列的大小。
随后L层地牢每层R行每行C个字符。 每个字符表示地牢的一个单元。’#‘表示岩石单元’.‘表示空白单元。你的起始位置在’S’出口为’E’。 每层地牢后都有一个空行。LR和C均为0时输入结束。 Output - 输出 每个迷宫对应一行输出。 如果可以逃生则输出如下 Escaped in x minute(s). x为最短脱离时间。
如果无法逃生则输出如下 Trapped! Sample Input - 输入样例 3 4 5 S… .###. .##… ###.# ##.## ##… #.### ####E
1 3 3 S## #E# 0 0 0 Sample Output - 输出样例 Escaped in 11 minute(s). Trapped!
分析与解答
有图的这种搜索先把图存到数组里三个方向移动每个方向可以往前往后走就写一个方向数组3*2*3的数组 然后把起点先push到queue里之后把每个移动的可能情况都考虑到每移动一次如果满足这个坐标没出现过这个坐标没越界这个坐标是可以移动的就push到queue里然后标记数组标记移动到的坐标并将step增加 这个层都放到queue之后下一次循环开始还是先取出第一个数然后继续
#include iostream
#include stdio.h
#include string.h
#include queue
#include algorithm
using namespace std;char map[35][35][35];
int vis[35][35][35];
int k,n,m,sx,sy,sz,ex,ey,ez;
int to[6][3] {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};struct node
{int x,y,z,step;
};int check(int x,int y,int z)
{if(x0 || y0 || z0 || xk || yn || zm)return 1;else if(map[x][y][z] #)return 1;else if(vis[x][y][z])return 1;return 0;
}int bfs()
{int i;node a,next;queuenode Q;a.x sx,a.y sy,a.z sz;a.step 0;vis[sx][sy][sz] 1;Q.push(a);while(!Q.empty()){a Q.front();Q.pop();if(a.x ex a.y ey a.z ez)return a.step;for(i 0; i6; i){next a;next.x a.xto[i][0];next.y a.yto[i][1];next.z a.zto[i][2];if(check(next.x,next.y,next.z))continue;vis[next.x][next.y][next.z] 1;next.step a.step1;Q.push(next);}}return 0;
}int main()
{int i,j,r;while(scanf(%d%d%d,k,n,m),nmk){for(i 0; ik; i){for(j 0; jn; j){scanf(%s,map[i][j]);for(r 0; rm; r){if(map[i][j][r] S){sx i,sy j,sz r;}else if(map[i][j][r] E){ex i,ey j,ez r;}}}}memset(vis,0,sizeof(vis));int ans;ans bfs();if(ans)printf(Escaped in %d minute(s).\n,ans);elseprintf(Trapped!\n);}return 0;
}
