poj 2251 Dungeon Master

点击打开链接

Description

Input

Output

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!

题意： 
 给出一三维空间的地牢,要求求出由字符‘S‘到字符‘E‘的最短路径

移动方向可以是东、西、南、北、上、下六个个方向

每移动一次就耗费一分钟，要求输出最快的走出时间。
不同L层的地图，相同RC坐标处是连通的

#无法行通

.代表路

题目分析：

  此题与hdoj 1242 Rescue 十分相似

 只不过这个题稍微复杂的是三维，其实也复杂不了多少，小心就是啦

代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 35
char map[MAX][MAX][MAX];
int step[MAX][MAX][MAX];
int L,R,C;
int sx,sy,sz,ex,ey,ez;
int f[][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
struct node
{
  int x;
  int y;
  int z;
  int time;
};
queue<node>q;

void input()
{
  for(int i=0;i<L;i++)
   for(int j=0;j<R;j++)
     for(int k=0;k<C;k++)
	 {
	   if(map[i][j][k]=='S')
	   {
	    sx=i;
		sy=j;
		sz=k;	
	   }
	   if(map[i][j][k]=='E')
	   {
	    ex=i;
		ey=j;
		ez=k;	
	   }
	   step[i][j][k]=-1;	
	 }	
}

int valid(int x,int y,int z)
{
	if(x>=0&&x<L&&y>=0&&y<R&&z>=0&&z<C)
	 return 1;
	else
	 return 0;
}

void BFS()
{
	node p1,p2;
	p1.x=sx;
	p1.y=sy;
	p1.z=sz;
	p1.time=0;
	step[p1.x][p1.y][p1.z]=0;
	
	while(!q.empty())
	q.pop();
	
	q.push(p1);
	while(!q.empty())
	{
	  p1=q.front();
	  q.pop();
	  
	  for(int i=0;i<6;i++)//注意这儿
	  {
	    p2.x=p1.x+f[i][0];
		p2.y=p1.y+f[i][1];	
		p2.z=p1.z+f[i][2];
    
		if(map[p2.x][p2.y][p2.z]!='#'&&valid(p2.x,p2.y,p2.z))
      	{
      	 p2.time=p1.time+1;
		  if(step[p2.x][p2.y][p2.z]==-1||p2.time<step[p2.x][p2.y][p2.z])
		  {
			q.push(p2);
			step[p2.x][p2.y][p2.z]=p2.time; 
		  }	
		}		
	  } 
	}
}

int main()
{
	while(~scanf("%d%d%d",&L,&R,&C),(L||R||C))
	{
	  for(int i=0;i<L;i++)
	    for(int j=0;j<R;j++)
	      scanf("%s",map[i][j]);
	      input();
	      BFS();
	      if(step[ex][ey][ez]==-1)
	       printf("Trapped!\n");
	     else
	      printf("Escaped in %d minute(s).\n",step[ex][ey][ez]);
	}
	return 0;
}

#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define MAX 35
char map[MAX][MAX][MAX];
int vis[MAX][MAX][MAX];
int step[MAX][MAX][MAX];
int L,R,C;
int sx,sy,sz;
int f[][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
struct node
{
  int x;
  int y;
  int z;
  int time;
};
queue<node>q;

void input()
{
  for(int i=0;i<L;i++)
   for(int j=0;j<R;j++)
     for(int k=0;k<C;k++)
	 {
	   if(map[i][j][k]=='S')
	   {
	    sx=i;
		sy=j;
		sz=k;	
	   }
	   vis[i][j][k]=0;	
	 }	
}

int valid(int x,int y,int z)
{
	if(x>=0&&x<L&&y>=0&&y<R&&z>=0&&z<C)
	 return 1;
	else
	 return 0;
}

void BFS()
{
	node p1,p2;
	p1.x=sx;
	p1.y=sy;
	p1.z=sz;
	p1.time=0;

	while(!q.empty())
	q.pop();
	
	vis[p1.x][p1.y][p1.z]=1;
	q.push(p1);
	while(!q.empty())
	{
	  p1=q.front();
	  q.pop();
	  
	  for(int i=0;i<6;i++)//注意这儿
	  {
	    p2.x=p1.x+f[i][0];
		p2.y=p1.y+f[i][1];	
		p2.z=p1.z+f[i][2];
    
		if(map[p2.x][p2.y][p2.z]!='#'&&valid(p2.x,p2.y,p2.z)&&!vis[p2.x][p2.y][p2.z])
      	{
      	 p2.time=p1.time+1;
		  if(map[p2.x][p2.y][p2.z]=='E')//此处直接返回值，不用那么复杂
		  { 
		   printf("Escaped in %d minute(s).\n",p2.time);
		   return ;
		  }	
		 vis[p2.x][p2.y][p2.z]=1;
		 q.push(p2);
		}		
	  } 
	}
	printf("Trapped!\n");
}

int main()
{
	while(~scanf("%d%d%d",&L,&R,&C),(L||R||C))
	{
	  for(int i=0;i<L;i++)
	    for(int j=0;j<R;j++)
	      scanf("%s",map[i][j]);
	      input();
	      BFS();
	}
	return 0;
}

poj 2251 Dungeon Master

原文：http://blog.csdn.net/lh__huahuan/article/details/47317503