18276 走迷宫

目录

Description

输入格式

输出格式

输入样例

输出样例


Description

有一个N*M的格子迷宫,1代表该格子为墙,不能通过,0代表可以通过,另外,在迷宫中
有一些传送门,走到传送门的入口即会自动被传送到传送门的出口(一次传送算1步)。人在迷宫中可以尝试
上下左右四个方向移动。现在给定一个迷宫和所有传送门的出入口,以及起点和终点,
问最少多少步可以走出迷宫。如果不能走出迷宫输出“die”。

输入格式

该程序为多CASE,第1行为CASE的数量
每一个CASE,第1行为两个数N(行)和M(列)
然后N行每行M个数
之后是一个数W,为传送门的数量
之后每行一个传送门的入口坐标c1(行),r1(列)和出口坐标c2,r2
之后是起点坐标和终点坐标sc(行) sr(列) ec(行) er(列)

注:传送门出入口和起点坐标和终点坐标不会出现在墙的位置
所有数字不超过100


 

输出格式

如题


 

输入样例

2
4 3
011
011
110
110
1
1 0 2 2
0 0 3 2
2 2
01
10
0
0 0 1 1


 

输出样例

3
die

 题意:

在具有传送门的迷宫中求出从起点到终点的最短步数。

分析:

如果是普通迷宫,我们就可以直接用bfs模板即可,加了传送门后就稍微有点麻烦。但仔细分析也不难。我们只要每次先判断当前队头是否为传送门即可,如果为传送门,则走到传送门的出口并将其入队,如果不是,则按照模板走四个方向即可


#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,w,c1,r1,c2,r2,sc,sr,ec,er;
char g[N][N];//存储地图
int d[N][N];//存储第i行第j列的步数
PII door[N][N];//存储传送门的入口和出口
void bfs(){

    memset(d,-1,sizeof(d));//初始化d为-1
    queue<PII>q;
    q.push({sc,sr});//将起点入队并将其步数初始化为0
    d[sc][sr]=0;
    PII t;
    while(!q.empty()){
        t=q.front();
        //cout<<t.x<<' '<<t.y<<endl;
        q.pop();
        //判断当前位置是否为传送门
        if(door[t.x][t.y].x!=-1&&door[t.x][t.y].y!=-1){
            d[door[t.x][t.y].x][door[t.x][t.y].y]=d[t.x][t.y]+1;
            //cout<<door[t.x][t.y].x<<' '<<door[t.x][t.y].y<<endl;
            int xx=t.x,yy=t.y; 
            t.x=door[xx][yy].x;
            t.y=door[xx][yy].y;
            q.push(t);
            continue;
        }
        //迷宫正常模板
        int dir[4][2]={0,1,0,-1,1,0,-1,0};
        for(int i=0;i<4;++i){
            //cout<<t.x<<' '<<t.y<<endl;
            int x=t.x+dir[i][0],y=t.y+dir[i][1];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]!='1'&&d[x][y]==-1){
                //cout<<x<<' '<<y<<endl;
                d[x][y]=d[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
}

int main()
{
    int kcase;
    cin>>kcase;
    while(kcase--){
        for(int i=0;i<=100;++i){
            for(int j=0;j<=100;++j){
                door[i][j].x=-1;
                door[i][j].y=-1;
            }
        }
        cin>>n>>m;
        for(int i=0;i<n;++i){
            cin>>g[i];
            getchar();
        }
        cin>>w;
        for(int i=0;i<w;++i){
            cin>>c1>>r1>>c2>>r2;
            door[c1][r1].x=c2;
            door[c1][r1].y=r2;
        }
        cin>>sc>>sr>>ec>>er;
        bfs();
        /*for(int i=0;i<4;++i){
            for(int j=0;j<3;++j){
                cout<<d[i][j]<<' ';
            }
            cout<<endl;
        }*/
        if(d[ec][er]==-1){
            cout<<"die"<<endl;
        }else{
            cout<<d[ec][er]<<endl;
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/2895.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【尝鲜版】ChatGPT插件开发指南

3月23日&#xff0c;OpenAI官方发布了一则公告&#xff0c;宣告ChatGPT已经支持了插件功能&#xff0c;现在处于内测阶段。插件的意义不仅仅在于功能的扩展&#xff0c;它直接让ChatGTP拥有了联网的能力&#xff01;简直是猛兽出笼、蛟龙出海&#xff0c;要让ChatGPT大杀特杀啊…

phpstorm断点调试

环境&#xff1a;win10phpstorm2022phpstudy8lnmp 1、phpinfo(); 查看是否安装xdebug&#xff0c;没有走以下流程 2、phpstudy中切换不同版本php版本&#xff0c;有些版本不支持xdebug&#xff08;如php8.0.2&#xff09;&#xff0c;有些已经自带了&#xff08;如php7.3.9&a…

Java奠基】Java经典案例讲解

目录 卖飞机票 找质数 开发验证码 数组元素的复制 评委打分 数字加密 数字解密 抢红包 模拟双色球 二维数组 卖飞机票 需求&#xff1a;机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格&#xff1a; 旺季&…

技术分享——Java8新特性

技术分享——Java8新特性1.背景2. 新特性主要内容3. Lambda表达式4. 四大内置核心函数式接口4.1 Consumer<T>消费型接口4.2 Supplier<T>供给型接口4.3 Function<T,R>函数型接口4.4 Predicate<T> 断定型接口5. Stream流操作5.1 什么是流以及流的类型5.2…

[攻城狮计划]如何优雅的在RA2E1上运行RT_Thread

文章目录[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread准备阶段&#x1f697;开发板&#x1f697;开发环境&#x1f697;下载BSP&#x1f697;编译烧录连接串口总结[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread &#x1f680;&#x1f680;开启攻城狮的成长之旅&#xff0…

【ChatGPT】教你搭建多任务模型

ChatGPT教你搭建多任务模型 You: tell me what’s your version of gpt ? ChatGPT: As an AI language model developed by OpenAI, I am based on the GPT (Generative Pretrained Transformer) architecture. However, my version is known as GPT-3.5, which is an updat…

数据泄漏防护 (DLP) 工具保护敏感数据

通过实时安全监控&#xff0c;通过端点&#xff08;即 USB、电子邮件、打印等&#xff09;检测、中断和防止敏感数据泄露。使用 DataSecurity Plus 的数据泄漏防护 &#xff08;DLP&#xff09; 工具保护敏感数据不被泄露或被盗。DataSecurity Plus 主要功能包括&#xff1a; …

Android APP检查设备是否为平板

正文 Android APP判断设备是否为平板的三种方法&#xff1a; 通过屏幕尺寸判断。一般来说&#xff0c;平板电脑的屏幕尺寸比手机大很多&#xff0c;可以根据屏幕的长宽比和尺寸等信息来区分设备类型。通过屏幕像素密度判断。一般来说&#xff0c;平板电脑的屏幕像素密度比手机…

Java开发一年不到,来面试居然敢开口要20K,面完连8K都不想给~

前言 我的好朋友兼大学同学老伍家庭经济情况不错&#xff0c;毕业之后没两年自己存了点钱加上家里的支持&#xff0c;自己在杭州开了一家网络公司。由于公司不是很大所以公司大部分的开发人员都是自己面试的&#xff0c;近期公司发展的不错&#xff0c;打算扩招也面试了不少人…

四级数据库工程师 刷真题错题整理(三)数据库原理

1.数据模型是对现实世界进行抽象的工具&#xff0c;它按算机系统的观点模于提数据库系统中信息表示和操作手段的形式框架&#xff0c;主要用于 DBMS 的实现&#xff0c;是数据库系统的核心和基础。其中&#xff0c;数据操作是对数据间的动态行为。 2.数据库的型是稳定的&#…

day38_JDBC

今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、数据库连接池 二、反射 三、封装DBUtil 零、 复习昨日 SQL注入 预处理语句 String sql "select * from user where id ?"; PreparedStat…

企业微信中如何拉黑?拉黑个人和群成员有什么区别?

企业微信既可以拉黑个人好友&#xff0c;又可以拉黑群好友。 1. 拉黑个人好友 拉黑好友通俗来说就是不想再接收到对方的信息&#xff0c;企业微信可以通过设置消息免打扰的方式来屏蔽对方的消息。 【客户聊天界面】-【右上角的小人标志】-【第一栏名称进入】-【右上角三点】…

C语言——动态内存管理 malloc、calloc、realloc、free的使用

目录 一、为什么存在动态内存分配 二、动态内存函数的介绍 2.1malloc和free 2.2calloc 2.3realloc 三、常见的动态内存错误 3.1对NULL指针的解引用操作 3.2对动态开辟空间的越界访问 3.3对非动态开辟的内存使用free释放 3.4使用free释放一块动态开辟内存的一部分 3.5…

奇安信_防火墙部署_透明桥模式

奇安信_防火墙部署_透明桥模式一、预备知识二、项目场景三、拓扑图四、基本部署配置1. 登录web控制台2.连通性配置3.可信主机配置4.授权导入5.特征库升级6.安全配置文件五、透明桥配置1. 创建桥2. 端口绑定桥3. 创建桥端口六、结语一、预备知识 安全设备接入网络部署方式 二、…

运算放大器:电压比较器

目录一、单限电压比较器二、滞回电压比较器三、窗口电压比较器最近在学习电机控制&#xff0c;遇到了与运算放大电路相关的知识&#xff0c;然而太久没有接触模拟电路&#xff0c;对该知识已经淡忘了&#xff0c;及时温故而知新&#xff0c;做好笔记&#xff0c;若有错误、不足…

字节跳动测试岗面试记:二面被按地上血虐,所幸Offer已到手...

在互联网做了几年之后&#xff0c;去大厂“镀镀金”是大部分人的首选。大厂不仅待遇高、福利好&#xff0c;更重要的是&#xff0c;它是对你专业能力的背书&#xff0c;大厂工作背景多少会给你的简历增加几分竞争力。 但说实话&#xff0c;想进大厂还真没那么容易。最近面试字…

3分钟阐述这些年我的 接口自动化测试 职业生涯经验分享

接口自动化测试学习教程地址&#xff1a;https://www.bilibili.com/video/BV1914y1F7Bv/ 你好&#xff0c;我是凡哥。 很高兴能够分享我的接口自动化测试经验和心得体会。在我目前的职业生涯中&#xff0c;接口自动化测试是我经常进行的一项任务。通过不断地学习和实践&#xf…

【C++】map 和 set

文章目录一、关联式容器与键值对1、关联式容器2、键值对 pair3、树形结构的关联式容器二、set1、set 的介绍2、set 的使用三、multiset四、map1、map 的介绍2、map 的使用五、multimap一、关联式容器与键值对 1、关联式容器 在C初阶的时候&#xff0c;我们已经接触了 STL 中的…

基于SpringBoot的酒店管理系统

系统环境 开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/i…

matplotlib参数详解

文章目录一、简介二、安装与调用三、绘图与风格设置3.1、绘图标记3.1.1、标记类型&#xff08;marker*&#xff09;3.1.2、标记大小、内部和边框颜色&#xff08;ms10、mfcr、mecg&#xff09;3.2、绘图线3.2.1、线类型&#xff08;linestyle--&#xff09;3.2.2、线宽&#xf…
最新文章