Dungeon Master 广度优先搜索算法

本文主要是介绍Dungeon Master 广度优先搜索算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

【题目描述】

这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘S’表示起点，‘E’表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，每次都只能移到相邻的空位，每次需要花费一分钟，求从起点到终点最少要多久。

【输入】

多组测试数据。

一组测试测试数据表示一个三维迷宫：

前三个数，分别表示层数、一个面的长和宽，后面是每层的平面图。前三个数据为三个零表示结束。

【输出】

最小移动次数。

【输入样例】

3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0

【输出样例】

Escaped in 11 minute(s).
Trapped!

【提示】

对于题目给出数据的含义就是输入l，r，c，分别代表迷宫有l层，每层长宽分别是c，r。对于数据以可以这样移动:

 (1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->

 (1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)

 共11步就可以到达终点 对于数据二明显不能到达，则输出Trapped！

 算法解析

一道三维的广搜，使用单个字符读入分析储存，之后bfs搜索

代码如下

#include<bits/stdc++.h>
using namespace std;
int dx[6]={1,0,-1,0,0,0};
int dy[6]={0,1,0,-1,0,0};
int dz[6]={0,0,0,0,1,-1};
bool a[50][50][50],bo;
int X1,Y1,Z1,X2,Y2,Z2,l,n,m;

struct node
{
	int x,y,z,d;
}h[4100000];

void bfs()
{
	int head=0,tail=1;
	h[1].x=X1;
	h[1].y=Y1;
	h[1].z=Z1;
	h[1].d=0;
	a[X1][Y1][Z1]=1;
	do
	{
		head++;
		for(int i=0;i<6;i++)
		{
			int x=h[head].x+dx[i];
			int y=h[head].y+dy[i];
			int z=h[head].z+dz[i];
			int d=h[head].d+1;
			if(!a[z][x][y]&&x>0&&x<=n&&y>0&&y<=m&&z>0&&z<=l)
			{
				tail++;
				h[tail].x=x;
				h[tail].y=y;
				h[tail].z=z;
				h[tail].d=d;
				a[z][x][y]=1; 
				if(x==X2&&y==Y2&&z==Z2)
				{
					cout<<"Escaped in "<<d<<" minute(s)."<<endl;
					bo=1;
					return;
				}
			}
		}
	}
	while(head<tail);
}

int main()
{
	while(cin>>l>>n>>m)
	{
		if(l==0)
			return 0;
		memset(a,0,sizeof(a));
		for(int i=1;i<=l;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=m;k++)
				{
					char ch;
					cin>>ch;
					if(ch=='#')
						a[i][j][k]=1;
					if(ch=='S')
					{
						X1=j;
						Y1=k;
						Z1=i;
					}
					if(ch=='E')
					{
						X2=j;
						Y2=k;
						Z2=i;
					}
				}
		bo=0;
		bfs();
		if(!bo)
			cout<<"Trapped!"<<endl;
	}
	return 0;
}

这篇关于Dungeon Master 广度优先搜索算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！