POJ - 2251 Dungeon Master解题报告

一个三维的图(30*30*30)，求出从起点S到终点E的最短距离（有可能走不到） '.'可以走，'#'不能走 。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 50
using namespace std;
char map[N][N][N]={0};
bool vis[N][N][N]={0};
int dis[N][N][N]={0};
int move[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int x,y,z;
struct point
{
	int x;int y;int z;
};
point e,s;
void input()
{
	char l;
	l=getchar();
	for(int i=1;i<=x;i++)
	{	
		for(int j=1;j<=y;j++)
		{
			for(int h=1;h<=z;h++)
			{
				scanf("%c",&map[i][j][h]);
				if(map[i][j][h]=='S')
				{
					s.x=i;
					s.y=j;
					s.z=h;
				}
				if(map[i][j][h]=='E')
				{
					e.x=i;
					e.y=j;
					e.z=h;
				}
			}
			l=getchar();
		}
		l=getchar();
	}
	
}
bool is_inmap(point t)
{
	if(t.x<=0||t.x>x)return 0;
	if(t.y<=0||t.y>y)return 0;
	if(t.z<=0||t.z>z)return 0;
	return 1;
}
void bfs()
{
	queue<point>poi;
	poi.push(s);
	vis[s.x][s.y][s.z]=1;
	while(!poi.empty())
	{
		for(int i=0;i<6;i++)
		{
			point t;
			t.x=poi.front().x+move[i][0];
			t.y=poi.front().y+move[i][1];
			t.z=poi.front().z+move[i][2];
			if(vis[t.x][t.y][t.z]==1)continue;
			if(!is_inmap(t))continue;
			if(map[t.x][t.y][t.z]=='#')continue;
			
			dis[t.x][t.y][t.z]=dis[poi.front().x][poi.front().y][poi.front().z]+1;
			vis[t.x][t.y][t.z]=1;
			poi.push(t);
		}
		poi.pop();
	}
}

int main()
{
	while(cin>>x>>y>>z)
	{
		if(x==0&&y==0&&z==0)break;
		memset(dis,0,sizeof(dis));
		memset(vis,0,sizeof(vis));
		input();
		bfs();
		if(dis[e.x][e.y][e.z]==0)cout<<"Trapped!"<<endl;
		else cout<<"Escaped in "<<dis[e.x][e.y][e.z]<<" minute(s)."<<endl;
	}
	
	
}