(POJ - 2251)Dungeon Master(bfs)

题目链接:2251 -- Dungeon Master (poj.org)

这是一个典型的bfs迷宫问题,只不过是三维的,唯一需要注意的就是输入要用cin,不要用scanf,因为有换行,其他没什么了,下面上代码:代码中有注释:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=32;
int t[N][N][N],dx[6]={0,0,1,-1,0,0},dy[6]={1,-1,0,0,0,0},dz[6]={0,0,0,0,1,-1};
char s[N][N][N];
bool vis[N][N][N];
int nl,nr,nc,el,er,ec;
struct node{
	int l,r,c;
};
int bfs(int l,int r,int c)
{
	//多组输入,记得初始化数组 
	memset(t,0x3f,sizeof t);
	memset(vis,false,sizeof vis);
	t[l][r][c]=0;
	vis[l][r][c]=true;
	queue<node>q;
	q.push({l,r,c});
	while(q.size())
	{
		node temp=q.front();
		q.pop();
		if(temp.c==ec&&temp.l==el&&temp.r==er) break; 
		for(int i=0;i<6;i++)//枚举下一步可以到达的6个位置 
		{
			int nz=temp.l+dz[i],nx=temp.r+dx[i],ny=temp.c+dy[i];
			if(nz>=1&&nz<=nl&&nx>=1&&nx<=nr&&ny>=1&&ny<=nc&&!vis[nz][nx][ny]&&s[nz][nx][ny]!='#')//判断位置是否走过以及是否合法 
			{
				vis[nz][nx][ny]=true;//标记为该位置已走过 
				t[nz][nx][ny]=t[temp.l][temp.r][temp.c]+1;//记录到达该位置的最短时间 
				q.push({nz,nx,ny});//将该位置入队 
			}
		}
	}
	return t[el][er][ec];
}
int main()
{
	while(1)
	{
		scanf("%d%d%d",&nl,&nr,&nc);
		if(nl==0&&nr==0&&nc==0) break;
		int bl,br,bc;
		for(int i=1;i<=nl;i++)
		for(int j=1;j<=nr;j++)
		for(int k=1;k<=nc;k++)
		{
			cin>>s[i][j][k];//因为有换行,读入一定要用cin 
			if(s[i][j][k]=='S') bl=i,br=j,bc=k;//记录起点 
			if(s[i][j][k]=='E') el=i,er=j,ec=k;//记录终点 
		}
		int ans=bfs(bl,br,bc);
		if(ans!=0x3f3f3f3f) printf("Escaped in %d minute(s).\n",ans);
		else puts("Trapped!");
	}
	return 0;
} 

上一篇:关于图的BFS与DFS算法的总结


下一篇:HDU3533 Escape(预处理+bfs)