倒霉倒霉倒霉(传送门 bfs 三维数组 递归 综合运用

这篇具有很好参考价值的文章主要介绍了倒霉倒霉倒霉(传送门 bfs 三维数组 递归 综合运用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

“啊!倒霉倒霉倒霉~”龙叔被困在一座大厦里了,可恶的瓦龙把这座大厦点燃了,他借机消灭龙叔。

这座大厦有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

样例输出

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • IPv6路由综合运用

    一、基础配置: SWA: sw1(config)#host swA swA(config)#ipv6 ena swA(config)# vlan 100 swA(config-vlan100)#int vlan 100 swA(config-if-vlan100)#ipv6 ena swA(config-vlan100)#ip add 172.16.1.1 255.255.255.252 swA(config-if-vlan100)#int e1/0/24 swA(config-if-ethernet1/0/24)#sw acc vlan 100

    2024年02月01日
    浏览(45)
  • 二叉树BFS/DFS及重要递归接口--拿下二叉树--拿下数据结构--拿到好offer

     堆是一种特殊的二叉树(完全二叉树),由于有堆排序等实际的需求,堆是由类似顺序表的结构实现的,这是为了方便堆能够通过下标找到parent和child,进行比较大小以及交换等操作。 这里我们建立二叉树的每个结点,包含左右孩子指针left和right,还有存储的数据data。 然后

    2023年04月08日
    浏览(53)
  • 写递归题目的思路

    第一个问题,什么时候对数据进行操作? 我们递归的过程中是一定要对数据结构进行处理的,包括两个时间段,递归时处理数据,和回溯时处理数据。它们的区别就是一个写在递归函数调用处上面,一个写在调用处下面,此时需要注意,如果直接return 递归函数,也是属于递

    2024年02月07日
    浏览(45)
  • eNSP综合实验:OSPF、DHCP、NAT等技术运用

    拓扑图 1、 SW1为PC1和PC2的DHCP服务器,AR2为PC3和PC4的DHCP服务器 2、PC1、PC2、PC3、PC4能够访问外网 3、外网能够访问内网的HTTP服务器和FTP服务器 SW1配置 SW2配置 AR1配置 AR2配置 AR3配置 1、内网PC1、PC2、PC3、PC4能够访问外网 2、外网Client通过公网IP访问内网HTTP服务器和FTP服务器 ISP配

    2024年02月11日
    浏览(40)
  • 【计算机二级Python】综合题目

    描述使用字典和列表型变量完成最有人气的明星的投票数据分析。投票信息由附件里的文件vote.txt给出, 一行只有一个明星姓名的投票才是有效票 。有效票中得票最多的明星当选最有人气的明星。 问题一:请统计 有效票张数 。在编程模板中补充代码完成程序。 像一行同时出现

    2024年02月07日
    浏览(48)
  • 第380场周赛挑战:二分,数位dp和KMP算法的综合运用

    比赛地址 卡在第三题了,应该看看第4题kmp套模版的 二分查找 : findMaximumNumber 函数使用二分查找法来查找符合条件的最大 num 。它初始化左边界 left 为 0,右边界 right 为 (k + 1) (x - 1) 。这个右边界是一个估计值,确保 num 的上界足够高。二分查找在满足条件 left + 1 right 的情况

    2024年02月02日
    浏览(58)
  • 图书管理借阅系统【Java简易版】Java三大特征封装,继承,多态的综合运用

    前言 前几篇文章讲到了Java的基本语法规则,今天我们就用前面学到的数组,类和对象,封装,继承,多态,抽象类,接口等做一个图书管理借阅系统。 Java语言是面向对象的,所以首先要分析完成这个图书管理系统,有哪些对象: 👱使用者User 📘书Book 📲操作Operation 使用者

    2024年02月14日
    浏览(44)
  • C //练习 4-12 运用printd函数的设计思想编写一个递归版本的itoa函数,即通过递归调用把整数转换为字符串。

    练习 4-12 运用printd函数的设计思想编写一个递归版本的itoa函数,即通过递归调用把整数转换为字符串。 注意:代码在win32控制台运行,在不同的IDE环境下,有部分可能需要变更。 IDE工具:Visual Studio 2010   代码块:

    2024年01月18日
    浏览(75)
  • C语言中一维数组及二维数组的运用

    int * p  = arr; int * q = arr[1]; 其中arr是数组名,代表了整个数组的首元素地址,这个是一个常量,放在常量存储区,所以在给int*p赋值的时候可以不用带,而下面的arr[1]则代表数组里的某一个元素,所以在赋值时要加上  有个例题: 下列运行结果  解析:首先看main函数里的第二

    2024年02月13日
    浏览(46)
  • 【Python百宝箱】Python黑客实践手册:综合运用工具保障您的数字世界安全

    在当今数字化时代,网络安全变得至关重要。随着技术的迅猛发展,网络威胁也在不断演进。本文将带领您深入探讨一系列流行的网络安全工具,重点关注它们如何通过Python脚本提供强大的漏洞扫描和渗透测试功能。从 nmap 到 Metasploit ,再到 Wireshark 和 Burp Suite ,我们将揭示

    2024年02月03日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包