欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 2251Dungeon Master(地牢大师)

程序员文章站 2022-03-14 08:45:12
...

问题

题意:

你被困在一个3D地牢,需要找到最快的出路!地牢是由单位立方体组成,可以或不可以用岩石填充。将一个单位向北,南,东,西,上或下移动需要一分钟。你不能对角地移动,迷宫被四周的坚实岩石包围。是逃生可能吗?如果是,需要多长时间?

输入

输入由多个地牢组成。每个地牢描述从包含三个整数L,R和C(大小都限制为30)的行开始。 L是组成地牢的等级数。 R和C是组成每个级别的计划的行和列的数量。 然后将跟随L个包含C个字符的R行块。每个字符描述地牢的一个单元格。充满岩石的细胞由’#’指示,空细胞由’。’表示。您的起始位置由“S”表示,出口由字母“E”表示。每个级别后面都有一个空白行。输入由L,R和C的三个零终止。

输出

每个迷宫生成一行输出。如果可以到达出口,打印一行表格在x分钟内逸出。其中x由逃脱所需的最短时间替代。 如果无法转义,请打印该行被困!

POJ 2251Dungeon Master(地牢大师)

问题分析

AC代码

·······#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int L,R,C; // L 地牢层数,每层 R行,C列

typedef struct{
	int x;
	int y;
	int z;
}Node;  //地牢坐标

char G[35][35][35];

queue<Node> Q; 			//队列
Node path[35][35][35]; //路径
int minutes;     //耗时
bool visit[35][35][35]; //标记数组

Node go[6] = {{1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1}};

int Jude(Node W){
	return W.x>=0 && W.x<R && W.y>=0 && W.y<C && W.z>=0 && W.z<L; 
}

void print(Node W,Node Start){
	if(W.x == Start.x  && W.y == Start.y && W.z == Start.z){
		minutes = 0;
		return ;
	}
	print(path[W.x][W.y][W.z],Start);
	minutes = minutes + 1;
} 

bool bfs(Node start, Node end){
		memset(visit, 0, sizeof(visit));
		Q.push(start);
		visit[start.x][start.y][start.z] = true;
		
		while(!Q.empty()){
			Node V, W;
			V = Q.front();
			Q.pop();
			
			for(int i = 0; i < 6; i++){ //向各个方向辐射 
			
				W.x = V.x + go[i].x;
				W.y = V.y + go[i].y;
				W.z = V.z + go[i].z;
				
				if(Jude(W) && G[W.x][W.y][W.z] != '#'){
					if(!visit[W.x][W.y][W.z])
					{
						if(W.x == end.x && W.y == end.y && W.z == end.z){
							path[W.x][W.y][W.z] = V;
							print(W,start);
							return true; 
						}
						Q.push(W);
						path[W.x][W.y][W.z] = V;
						visit[W.x][W.y][W.z] = true;
					}
					
				}
			}
			
			
		}
	return false;
}

 
int main(){
	
	while(true){
		while(!Q.empty())
		{
			Q.pop();
		}
		Node start,end;
	
		cin>>L>>R>>C;   //输入L,R,C
		if(L == 0 && R==0 && C ==0 ) break; 
		if(L == 0 || R==0 || C ==0 ) {
			cout<<"Trapped!"<<endl; 
			continue;
		}
		for(int z = 0; z < L; z++){            //输入迷宫类型 
			for(int x = 0; x < R; x++){
				for(int y = 0; y < C; y++){
					cin>>G[x][y][z];
					if(G[x][y][z] == 'S'){
						start.x = x;
						start.y = y;
						start.z = z;
					}
					if(G[x][y][z] == 'E'){  //寻找出口位置的坐标 
						end.x = x;
						end.y = y;
						end.z = z;
					}
				}
			}
		}
		if(bfs(start,end)) printf("Escaped in %d minute(s).\n",minutes);
		else cout<<"Trapped!"<<endl; 
		
	}
	return 0;
}