当前位置: 首页 > news >正文

1112. 迷宫(DFS之连通性模型)

1112. 迷宫 - AcWing题库

一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 n∗n 的格点组成,每个格点只有2种状态,.#,前者表示可以通行后者表示不能通行。

同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。

如果起点或者终点有一个不能通行(为#),则看成无法办到。

注意:A、B不一定是两个不同的点。

输入格式

第1行是测试数据的组数 k,后面跟着 k 组输入。

每组测试数据的第1行是一个正整数 n,表示迷宫的规模是 n∗n 的。

接下来是一个 n∗n 的矩阵,矩阵中的元素为.或者#

再接下来一行是 4 个整数 ha,la,hb,lb,描述 A 处在第 ha 行, 第 la 列,B 处在第 hb 行, 第 lb 列。

注意到 ha,la,hb,lb 全部是从 0 开始计数的。

输出格式

k行,每行输出对应一个输入。

能办到则输出“YES”,否则输出“NO”。

数据范围

1≤n≤100

输入样例:
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
输出样例:
YES
NO

解析 :

使用dfs进行判断代码要比bfs简洁

dfs代码:

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e2 + 2;
int n, ha, la, hb, lb;
char str[N][N];
bool vis[N][N];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
bool dfs(int x, int y) {if (str[x][y] == '#')return false;if (x == hb && y == lb)return true;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= n)continue;if (vis[a][b])continue;vis[a][b] = 1;if (dfs(a, b))return true;}return false;
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; i++) {scanf("%s", str[i]);}cin >> ha >> la >> hb >> lb;memset(vis, 0, sizeof vis);if (dfs(ha, la))cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

BFS代码:

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e2 + 2;
int n,ha,la,hb,lb;
char str[N][N];
typedef pair<int, int> PII;
bool vis[N][N];string bfs() {string ret1 = "YES", ret2 = "NO";if (str[ha][la] == '#' || str[hb][lb] == '#')return ret2;int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };memset(vis, 0, sizeof vis);queue<PII>q;q.push({ ha,la });vis[ha][la] = 1;while (!q.empty()) {auto t = q.front();q.pop();if (t.first == hb && t.second == lb)return ret1;for (int i = 0; i < 4; i++) {int a = t.first + dx[i], b = t.second + dy[i];if (a < 0 || a >= n || b < 0 || b >= n)continue;if (str[a][b] == '#'||vis[a][b])continue;vis[a][b] = 1;q.push({ a,b });}}return ret2;
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 0; i < n; i++) {scanf("%s", str[i]);}cin >> ha >> la >> hb >> lb;cout << bfs() << endl;}return 0;
}

相关文章:

1112. 迷宫(DFS之连通性模型)

1112. 迷宫 - AcWing题库 一天Extense在森林里探险的时候不小心走入了一个迷宫&#xff0c;迷宫可以看成是由 n∗n 的格点组成&#xff0c;每个格点只有2种状态&#xff0c;.和#&#xff0c;前者表示可以通行后者表示不能通行。 同时当Extense处在某个格点时&#xff0c;他只…...

飞天使-k8s知识点1-kubernetes架构简述

文章目录 名词功能要点 k8s核心要素CNCF 云原生框架简介k8s组建介绍 名词 CI 持续集成, 自动化构建和测试&#xff1a;通过使用自动化构建工具和自动化测试套件&#xff0c;持续集成可以帮助开发人员自动构建和测试他们的代码。这样可以快速检测到潜在的问题&#xff0c;并及早…...

linux中deadline调度原理与代码注释

简介 deadline调度是比rt调度更高优先级的调度&#xff0c;它没有依赖于优先级的概念&#xff0c;而是给了每个实时任务一定的调度时间&#xff0c;这样的好处是&#xff1a;使多个实时任务场景的时间分配更合理&#xff0c;不让一些实时任务因为优先级低而饿死。deadline调度…...

jquery、vue、uni-app、小程序的页面传参方式

jQuery、Vue、Uni-app 和小程序&#xff08;例如微信小程序&#xff09;都有它们自己的页面传参方式。下面分别介绍这几种方式的页面传参方式&#xff1a; jQuery: 在jQuery中&#xff0c;页面传参通常是通过URL的查询参数来实现的。例如&#xff1a; <a href"page2…...

ModuleNotFoundError: No module named ‘openai.error‘

ModuleNotFoundError: No module named ‘openai.error’ result self.fn(*self.args, **self.kwargs) File “H:\chatGPTWeb\chatgpt-on-wechat\channel\chat_channel.py”, line 168, in _handle reply self._generate_reply(context) File “H:\chatGPTWeb\chatgpt-on-wec…...

理解pom.xml中的parent标签

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 循序渐进学SpringBoot ✨特色专栏&…...

element ui el-avatar 源码解析零基础逐行解析

avatar功能介绍 快捷配置头像的样式 avatar 的参数配置 属性说明参数size尺寸type string 类型 &#xff08;‘large’,‘medium’,‘small’&#xff09;number类型 validator 校验shape形状circle (原型) square&#xff08;方形&#xff09;icon传入的iconsrc传入的图片st…...

Linux下c语言实现动态库的动态调用

在Linux操作系统下&#xff0c;有时候需要在不重新编译程序的情况下&#xff0c;运行时动态地加载库&#xff0c;这时可以通过Linux操作系统提供的API可以实现&#xff0c;涉及到的API主要有dlopen、dlsym和dlclose。使用时&#xff0c;需要加上头文件#include <dlfcn.h>…...

为什么MCU在ADC采样时IO口有毛刺?

大家在使用MCU内部ADC进行信号采样一个静态电压时&#xff0c;可能在IO口上看到这样的波形。这个时候大家一般会认识是信号源有问题&#xff0c;但仔细观察会发现这个毛刺的频率是和ADC触发频率一样的。 那么为什么MCU在ADC采样时IO口会出现毛刺呢&#xff1f;这个毛刺对结果有…...

C# 将 Word 转化分享为电子期刊

目录 需求 方案分析 相关库引入 关键代码 Word 转 Pdf Pdf 转批量 Jpeg Jpeg 转为电子书 实现效果演示 小结 需求 曾经的一个项目&#xff0c;要求实现制作电子期刊定期发送给企业进行阅读&#xff0c;基本的需求如下&#xff1a; 1、由编辑人员使用 Microsoft Word…...

网络世界的黑暗角落:常见漏洞攻防大揭秘

网络世界的黑暗角落&#xff1a;常见漏洞攻防大揭秘 今天带来了网站常见的漏洞总结,大家在自己的服务器上也需要好好进行防护,密码不要过于简单.不然非常容易遭到攻击,最终达到不可挽回的损失.很多黑客想网络乞丐一样将你服务器打宕机,然后要求你进行付费.不知道大家有没有遇到…...

通信领域发展方向

5G网络技术&#xff1a;随着5G网络的建设和商用推广&#xff0c;各家运营商、厂商和研究机构都在探索5G技术的应用场景和解决方案&#xff0c;如网络切片、毫米波通信、多用户MIMO等。 物联网技术&#xff1a;物联网技术已经成为通信行业的重点发展领域&#xff0c;包括传感器…...

21 3GPP中 5G NR高速列车通信标准化

文章目录 信道模型实验——物理层设计相关元素μ(与子载波间隔有关)设计参考信号(DMRS) 本文提出初始接入、移动性管理、线性小区设计等高层技术。描述3GPP采用HST场景的评估参数&#xff0c;阐释了HST应用的物理层技术&#xff0c;包括数字通信和参考信号设计&#xff0c;链路…...

【网络安全】-Linux操作系统—CentOS安装、配置

文章目录 准备工作下载CentOS创建启动盘确保硬件兼容 安装CentOS启动安装程序分区硬盘网络和主机名设置开始安装完成安装 初次登录和配置更新系统安装额外的软件仓库安装网络工具配置防火墙设置SELinux安装文本编辑器配置SSH服务 总结 CentOS是一个基于Red Hat Enterprise Linu…...

CCNP课程实验-OSPF-CFG

目录 实验条件网络拓朴需求 配置实现基础配置1. 配置所有设备的IP地址 实现目标1. 要求按照下列标准配置一个OSPF网络。 路由协议采用OSPF&#xff0c;进程ID为89 &#xff0c;RID为loopback0地址。3. R4/R5/R6相连的三个站点链路OSPF网络类型配置成广播型&#xff0c;其中R5路…...

【Spring Security】打造安全无忧的Web应用--入门篇

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Spring Security的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.Spring Security是什么 1.概…...

【每日一题】【12.20】2828.判别首字母缩略词

&#x1f525;博客主页&#xff1a; A_SHOWY&#x1f3a5;系列专栏&#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_ 1.题目链接 2828. 判别首字母缩略词https://leetcode.cn/problems/check-if-a-string-is-an-acronym-of-words/ 2.题目描述 今天…...

LabVIEW开发振动数据分析系统

LabVIEW开发振动数据分析系统 自动测试系统基于LabVIEW平台设计&#xff0c;采用了多种高级硬件设备。系统的硬件组成包括PCB振动加速度传感器&#xff0c;这是一种集成了传统压电加速度传感器和电荷放大器的先进设备&#xff0c;能够直接与采集仪器连接。此外&#xff0c;系统…...

去掉乘法运算的加法移位神经网络架构

[CVPR 2020] AdderNet: Do We Really Need Multiplications in Deep Learning? 代码&#xff1a;https://github.com/huawei-noah/AdderNet/tree/master 核心贡献 用filter与input feature之间的L1-范数距离作为“卷积层”的输出为了提升模型性能&#xff0c;提出全精度梯度…...

【TB作品】51单片机,具有报时报温功能的电子钟

2.具有报时报温功能的电子钟 一、功能要求: 1.显示室温。 2.具有实时时间显示。 3.具有实时年月日显示和校对功能。 4.具有整点语音播报时间和温度功能。 5.定闹功能,闹钟音乐可选。 6.操作简单、界面友好。 二、设计建议: 1.单片机自选(C51、STM32或其他单片机)。 2.时钟日历芯…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...