首页 > 代码库 > POJ_2251（初识广搜）

POJ_2251（初识广搜）

2024-11-24 13:25:39   203人阅读

 
Description
 
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take?
 
Input
 
The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size).
L is the number of levels making up the dungeon.
R and C are the number of rows and columns making up the plan of each level.
Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘#‘ and empty cells are represented by a ‘.‘. Your starting position is indicated by ‘S‘ and the exit by the letter ‘E‘. There‘s a single blank line after each level. Input is terminated by three zeroes for L, R and C.
 
Output
 
Each maze generates one line of output. If it is possible to reach the exit, print a line of the form        Escaped in x minute(s).
where x is replaced by the shortest time it takes to escape.
If it is not possible to escape, print the line       Trapped！
 
Sample Input 
3 4 5
S....
.###.
.##..
###.#

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

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

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

0 0 0
Sample Output 
Escaped in 11 minute(s).
Trapped!

这是一个迷宫问题，并且是3D的就是多了个一维度，问从起点S开始所能走到E便成功逃离输出需要多少秒，否则不能逃离。
搜索菜鸟，只会深搜的我TLE了，学长教了一遍广搜，有所领悟吧！
有一个需要注意的地方是，起点不一定是mp[0][0][0]。需要自己搜一下起点位置，在这个地方wa了好几次。

https://vjudge.net/contest/178007#problem/B
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 35;
char mp[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];
int dis[6][3]={-1,0,0, 1,0,0, 0,-1,0, 0,0,-1, 0,0,1, 0,1,0};
int n,m,c;

struct Node{
	int x,y,z,step;
};

queue<Node> q;

int bfs(){
	while(!q.empty()){
		Node k,f;
		k=q.front();
		q.pop();
		if(mp[k.x][k.y][k.z]==‘E‘)
			return k.step;
		for(int i=0;i<6;i++){
			int xx=k.x+dis[i][0];
			int yy=k.y+dis[i][1];
			int zz=k.z+dis[i][2];
			if(xx>=0&&yy>=0&&zz>=0&&xx<n&&yy<m&&zz<c&&vis[xx][yy][zz]==0&&mp[xx][yy][zz]!=‘#‘){
				vis[xx][yy][zz]=1;
				f.x=xx; f.y=yy; f.z=zz;
				f.step=k.step+1;
				q.push(f);
			}
		}	
	}
	return 0;
}

int main(){
	
	while(scanf("%d %d %d",&n,&m,&c)==3&&n&&m&&c){
		memset(vis,0,sizeof(vis));
		while(!q.empty()) q.pop();
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				scanf("%s",mp[i][j]);
				for(int k=0;k<c;k++){
					if(mp[i][j][k]==‘S‘){
						vis[i][j][k]=1;
						Node s;
						s.x=i; s.y=j; s.z=k; s.step=0;
						//vis[s.x][s.y][s.z]=1;
						q.push(s);
					}
				}
			}	
		}
		int ans;
		ans = bfs();
		if(ans!=0)
			printf("Escaped in %d minute(s).\n",ans);
		else
			printf("Trapped!\n");
	}
	return 0;
}

 

POJ_2251（初识广搜）


联系
我们