poj2251 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!

记得之前是看题解才做出来的，今天又做了一遍，1A,果然题目多做是有好处的。这道题是三维的，其实就是在二维的基础上加了z轴，所以用bfs的时候用6个方向。

#include<stdio.h>
#include<string.h>
int x2,y2,z2,x3,y3,z3;
char map[40][40][40];
int b[40][40][40];
int tab[8][3]={1,0,0, -1,0,0, 0,0,1, 0,-1,0, 0,0,-1, 0,1,0},num,flag,m,n,l;
int q[1111111][3];
void bfs()
{
	memset(q,0,sizeof(q));
	memset(b,0,sizeof(b));
	int front=1,rear=1,i,j,x,y,z,xx,yy,zz;
    q[front][0]=z2;q[front][1]=x2;q[front][2]=y2;
    b[z2][x2][y2]=0;
	while(front<=rear)
	{
		z=q[front][0];x=q[front][1];y=q[front][2];
		if(x==x3 && y==y3 && z==z3) return;
		front++;
		for(i=0;i<6;i++){
				xx=x+tab[i][1];yy=y+tab[i][2];zz=z+tab[i][0];
				if(xx>=0 && xx<n && yy>=0 && yy<m && zz>=0 && zz<l && map[zz][xx][yy]!=‘#‘)
				{
					map[zz][xx][yy]=‘#‘;
					b[zz][xx][yy]=b[z][x][y]+1;
					rear++;
					q[rear][0]=zz;q[rear][1]=xx;q[rear][2]=yy;
				}
		}
	}
	return;
}


int main()
{
	int i,j,h;
	while(scanf("%d%d%d",&l,&n,&m)!=EOF)
	{
		if(n==0 && m==0 && l==0)break;
		memset(map,0,sizeof(map));
		for(h=0;h<l;h++){
			for(i=0;i<n;i++){
				scanf("%s",map[h][i]);
				for(j=0;j<m;j++){
					if(map[h][i][j]==‘S‘){
						x2=i;y2=j;z2=h;
					}
					else if(map[h][i][j]==‘E‘){
						x3=i;y3=j;z3=h;
					}
				}
			}
		}
			num=0;flag=0;
			map[z2][x2][y2]=‘#‘;
			bfs();
			if(b[z3][x3][y3]==0){
				printf("Trapped!\n");continue;
			}
			printf("Escaped in %d minute(s).\n",b[z3][x3][y3]);
	}
	return 0;
}

poj2251 Dungeon Master

原文：http://blog.csdn.net/kirito_acmer/article/details/45462819