题目描述
“啊!倒霉倒霉倒霉~”龙叔被困在一座大厦里了,可恶的瓦龙把这座大厦点燃了,他借机消灭龙叔。
这座大厦有L层,每一层都有R*C个房间。熊熊火焰蔓延十分快,有的房间已经着火了,龙叔没办法通过。
这时老爹用魔法告诉龙叔,这座大厦出口的位置。“还有一件事,成龙,我用魔法在大厦里开了几个传送门,任意两个传送门是互通的,你进入其中一个传送门,并从另一个传送门出来。还有一件事,老爹的咖啡没了,你快来给老爹泡咖啡”。
这座大厦的每一层楼都可以用一个R*C的字符矩阵来表示,
如果第i行j列的字符为S,表示这是龙叔现在的位置,
如果第i行j列的字符为E,表示这是大厦的出口,
如果第i行j列的字符是C,表示这是一个传送门,
如果第i行j列的字符是’.’,表示这个房间可以通行,
如果第i行j列的字符是”#”,表示这个房间着火了,不可以通行。
一共有L个矩阵
当龙叔在某一个房间时,龙叔可以到达前后左右上下6个房间,且龙叔从一个房间到达另一个房间需要一分钟。
龙叔从一个传送门到达另一个传送门需要一分钟。
注意, 传送门不会和起点S, 出口E, 或着火点#重叠。
注意,起点S和出口E不会重叠,且两者都不会着火。
注意,当龙叔遇到传送门时,他不一定要使用传送门。
输入格式
第一行有三个整数,L,R,C,含义与题面描述一致,且大小均不超过30。
接下有L个R行C列的矩阵,每两个矩阵之间有一个空行。
输出格式
如果龙叔能逃离大厦,输出龙叔逃出大厦的最小时间,否则输出-1.
样例输入
3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E文章来源:https://www.toymoban.com/news/detail-417507.html
样例输出
11文章来源地址https://www.toymoban.com/news/detail-417507.html
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int maxx = 1000050;
int n, m, k, t, now, p, l, r, c, b;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
char e[50][50][50];
int step[50][50][50];
int nx, ny, nz, ex, ey, ez;
int dx[] = { -1 , 1 ,0 , 0 , 0 , 0 };//每个可能位移的方位
int dy[] = { 0 , 0 , 1 , -1 , 0 , 0 };
int dz[] = { 0 , 0 , 0 , 0 , -1 , 1 };
struct check//用来储存坐标的结构体
{
int x, y, z;
check(int xx = 0, int yy = 0, int zz = 0)
{
x = xx;
y = yy;
z = zz;
}
};
vector<check> csm;//这个数组是用来储存传送门的
int bfs()//在这里我们应该明白 n系列的如nx 为这一步坐标,而p系列的如px 为上一步的坐标
{
memset(step, 0x3f, sizeof(step));//将步数数组初始化
queue <check> q;
q.push(check(nx, ny, nz));//将起点也推入队列 , 这个队列也是用来储存步数的
step[nx][ny][nz] = 0;//每当前这步都进行初始化
bool chuan = false;
while (!q.empty())//只要不为空(也就是所有的能走的路都走无光的话
{
check p = q.front();//将队顶的取出
q.pop();//取出之后就可以将其推出队列
if (e[p.x][p.y][p.z] == 'E')//当其遍历到终点时
{
return step[p.x][p.y][p.z] ;//返回这个步数
}
for (int i = 0; i < 6; i++)
{
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int nz = p.z + dz[i];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < l && ny < r && nz < c)//没有越界的话
{
if (e[nx][ny][nz] != '#' && step[nx][ny][nz] > step[p.x][p.y][p.z] + 1)
{
q.push(check(nx, ny, nz));//将其坐标进行储存
step[nx][ny][nz] = step[p.x][p.y][p.z] + 1;//如今的步数为当之前的步数++
}
}
}
//需要注意的是,这个只是考虑了没有传送门的情况
//所以传送门是需要另外考虑的
if (e[p.x][p.y][p.z] == 'C' && chuan == false)//chuan为false代表并未使用
{
chuan = true;//传送门被使用啦
for (int i = 0; i < csm.size(); i++)// 从头开始遍历传送门的可能性
{//因为任意俩传送门互通
int nx = csm[i].x;
int ny = csm[i].y;
int nz = csm[i].z;
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < l && ny < r && nz < c)
{
if (e[nx][ny][nz] != '#' && step[nx][ny][nz] > step[p.x][p.y][p.z] + 1)
{//如果步数比前一步 +1 步更多的话
q.push(check(nx, ny, nz));
step[nx][ny][nz] = step[p.x][p.y][p.z] + 1;
}
}
}
}
}
return -1;//当其并未因为出口出去时就会返回 - 1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> l >> r >> c;
for (int i = 0; i < l; i++)
{
for (int j = 0; j < r; j++)
{
for (int k = 0; k < c; k++)
{
char v;
cin >> v;
e[i][j][k] = v;
if (v == 'S')//如果为入口
{
nx = i;//存入当前这步(n系列//重点
ny = j;
nz = k;
}
if (v == 'C')//如果为传送门
{
csm.push_back(check(i, j, k));//存入动态数组
}
}
}
}
cout << bfs() << endl;//输出答案
return 0;
}
到了这里,关于倒霉倒霉倒霉(传送门 bfs 三维数组 递归 综合运用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!