dfs,CF 196B - Infinite Maze

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

https://codeforces.com/problemset/problem/196/B


二、解题报告

1、思路分析

考虑如何判断一条路径可以无限走?

我们对朴素的网格dfs改进,改进为可以dfs网格外的区域

如果存在某个 位置 (i % n, j % m) 被访问两次,并且两次的(i, j)不同,则说明进入了一条路径的循环,合法。

2、复杂度

时间复杂度: O(NM)空间复杂度:O(NM)

3、代码详解

 ​
#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1e-9;struct DSU {std::vector<int> p;int n;DSU(int _n) : p(_n, -1), n(_n) {}void init () {p.assign(n, -1);}int find(int x) {return p[x] < 0 ? x : p[x] = find(p[x]);}void merge(int x, int y) {int px = find(x), py = find(y);if (px == py) return;if (p[px] > p[py]) std::swap(px, py);p[px] += p[py], p[py] = px;}int size(int x) {return -p[find(x)];}
};constexpr int dir[5] = { -1, 0, 1, 0, -1 };void solve() {int n, m;std::cin >> n >> m;std::vector<std::string> g(n);for (int i = 0; i < n; ++ i) std::cin >> g[i];if (n == 1 && m == 1) {std::cout << "Yes";return;}int stx, sty;for (int i = 0; i < n; ++ i)for (int j = 0; j < m; ++ j) if (g[i][j] == 'S') {stx = i, sty = j;break;}auto pos = [&m](int i, int j) {return i * m + j;};std::vector<std::pair<int, int>> st, vis(n * m, { inf32, inf32 });st.emplace_back(stx, sty);vis[pos(stx, sty)] = { stx, sty };while (st.size()) {auto [x, y] = st.back();st.pop_back();for (int k = 0; k < 4; ++ k) {auto [nx, ny] = std::pair(x + dir[k], y + dir[k + 1]);auto [nnx, nny] = std::pair(((nx % n) + n) % n, ((ny % m) + m) % m);// assert(nnx >= 0 && nnx < n);// assert(nny >= 0 && nny < m);if (g[nnx][nny] != '#') {if (vis[pos(nnx, nny)].first < inf32) {if(vis[pos(nnx, nny)] != std::pair(nx, ny)) {std::cout << "Yes";return;}}else {vis[pos(nnx, nny)] = { nx, ny };st.emplace_back(nx, ny);}}}}std::cout << "No";
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

免费分享:全国传统村落空间分布数据(附下载方法)

数据简介 本数据是在中国传统村落名录的基础上&#xff0c;通过地理编码&#xff0c;制作成具有空间坐标信息的矢量数据。 数据属性 数据名称&#xff1a;全国传统村落空间分布数据数据时间&#xff1a;2012年至今&#xff0c;更新至第五批空间位置&#xff1a;全国数据格式&…

模拟自然光照:饮料稳定性测试的创新方法

饮料添加剂的光照稳定性测试旨在评估其在光照影响下的保持稳定性的能力&#xff0c;特别是在储存期间。此测试有助于制造商理解饮料在不同光源作用下的变化&#xff0c;例如颜色、口感、香气等感官性质的变化&#xff0c;以及营养成分的衰变速率。这些信息对改进产品配方、包装…

与树莓派的“黄金”关系,是如何帮助这家医疗设备公司扩大规模

稳定的供应和与Raspberry Pi的“黄金”关系帮助医疗设备公司进行了规模扩张 埃及医疗设备制造商Bio Business需要将物联网功能集成到其成功的患者监测设备系列中。Raspberry Pi技术使他们得以实现。 解决方案 RP2040 Compute Module 4 企业规模 中小企业 行业 医疗技术 …

怎么挑选适合企业的安全管理软件?2024值得推荐的5款安全管理软件?

在企业安全管理时&#xff0c;你是否遇到过以下问题&#xff1a; 工作点多面广&#xff0c;信息整理和分析的工作量大&#xff0c;手工处理繁杂耗时&#xff1b; 传统巡检方式&#xff0c;无法保证巡检过程结果真实性&#xff1b; 纸质记录不清晰&#xff0c;问题改进缺乏数…

使用SpaceDesk实现iPad成为电脑拓展屏(保姆级教程)

使用SpaceDesk实现iPad成为电脑拓展屏 SpaceDesk是一个开源的软件, 所以说对学生和平民用户非常的友好, 连接后的画质也非常不错, 而且具有无线和有线两种连接方式. 接下来就开始教程: 1. 安装SpaceDesk电脑版 首先我们要下载SpaceDesk电脑版安装好: SpaceDesk官网 注意: …

2006-2022年中国农村经营管理年报

2006-2022年中国农村经营管理年报 1、时间&#xff1a;2006-2022年 2、格式&#xff1a;2006-2014年为EXCEL&#xff0c;2015-2022年为PDF 3、说明&#xff1a;根据农村经营管理情况统计报表制度调查数据整理、编辑的。本资料系统收录了全国各省、自治区、直辖市农村集体经济…

https执行过程,特点,作用

还是大剑师兰特&#xff1a;曾是美国某知名大学计算机专业研究生&#xff0c;现为航空航海领域高级前端工程师&#xff1b;CSDN知名博主&#xff0c;GIS领域优质创作者&#xff0c;深耕openlayers、leaflet、mapbox、cesium&#xff0c;canvas&#xff0c;webgl&#xff0c;ech…

【Spring Boot】手撕搜索引擎项目,深度复盘在开发中的重难点和总结(长达两万6千字的干货,系好安全带,要发车了......)

目录 搜索引擎搜索引擎的核心思路 一、解析模块1.1 枚举所有文件1.2 解析每个文件的标题&#xff0c;URL以及正文1.2.1 解析标题1.2.2 解析URL1.2.3 解析正文 1.3 线程池优化代码 二 、创建排序模块2.1 构建正排索引2.2 构建倒排索引2.3 序列化2.4 反序列化 三、搜索模块3.1 引…

86. UE5 RPG 技能面板实现监听数据

在上一篇文章里&#xff0c;我们创建了技能面板的控制器&#xff0c;接下来&#xff0c;我们将实现通过控制器绑定委托&#xff0c;来更新显示内容。 更新技能面板应用的技能 我们首先更新技能面板上面已经应用的技能&#xff0c;让其和WBP_Overlay上面一样&#xff0c;可以更…

ELK+filebeat

ELKfilebeat 一、filebeat概述 1、filebeat概念&#xff1a; filebeat日志收集工具和logstash相同 filebeat是一款轻量级的日志收集工具&#xff0c;可以在非JAVA环境下运行。 因此&#xff0c;filebeat常被用在非JAVAf的服务器上用于替代Logstash&#xff0c;收集日志信息。…

产品经理NPDP好考吗?

NPDP是新产品开发专业人员的资格认证&#xff0c;对于希望在产品管理领域取得认可的专业人士来说&#xff0c;NPDP认证是一项重要的资格。 那么&#xff0c;产品经理考取NPDP资格认证究竟难不难呢&#xff1f; 首先&#xff0c;NPDP考试的难易程度取决于考生的背景和准备情况…

谷粒商城实战笔记-105~107-全文检索-ElasticSearch-入门

文章目录 一&#xff0c;105-全文检索-ElasticSearch-入门-_cat二&#xff0c;106-全文检索-ElasticSearch-入门-put&post新增数据三&#xff0c;107-全文检索-ElasticSearch-入门-get查询数据&乐观锁字段1&#xff0c;过时的乐观锁-version2&#xff0c;Elasticsearch…

计算机网络知识点面试总结4

#来自ウルトラマンゼロ&#xff08;赛罗&#xff09; 1 传输层提供的服务 1.1 功能 传输层向它上面的应用层提供通信服务&#xff0c;它属于面向部分的最高层&#xff0c;同时也是用户功能中的最底层。 为运行在不同主机上的进程之间提供了逻辑通信。 传输层的功能&#xff1…

【教程】从零开始用QT简易实现modbus通信

前言&#xff1a;本文旨在让读者了解在qt6中实现modbus通信主要使用哪些函数&#xff0c;需要引用哪些库和头文件&#xff0c;不对modbus协议进行介绍&#xff0c;仅在代码层面简单实现一个modbus通信案例 实现效果&#xff1a;点击读取按钮可以读取从机中的十个寄存器&#x…

【QT】鼠标按键事件 - QMouseEvent QKeyEvent

qt 事件 事件1. 事件概念2. 事件的处理3. 按键事件&#xff08;1&#xff09;单个按键&#xff08;2&#xff09;组合按键 4. 鼠标事件&#xff08;1&#xff09;鼠标单击事件&#xff08;2&#xff09;鼠标释放事件&#xff08;3&#xff09;鼠标双击事件&#xff08;4&#x…

【数据分析】统计学基础及Python具体实现

各位大佬好 &#xff0c;这里是阿川的博客&#xff0c;祝您变得更强 个人主页&#xff1a;在线OJ的阿川 大佬的支持和鼓励&#xff0c;将是我成长路上最大的动力 阿川水平有限&#xff0c;如有错误&#xff0c;欢迎大佬指正 Python 初阶 Python–语言基础与由来介绍 Python–…

【Python】已解决:ERROR: Could not install packages due to an OSError: [WinError 5] 拒绝访问。: ‘e:\anaconda\in

文章目录 一、分析问题背景二、可能出错的原因三、错误代码示例四、正确代码示例五、注意事项 已解决&#xff1a;ERROR: Could not install packages due to an OSError: [WinError 5] 拒绝访问。: ‘e:\anaconda\install_root\scripts\pip.exe’ Consider using the --user o…

C语言详解(结构体)

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#xff0c;在这里撰写成文一…

【MAVEN】如何解决“Error unmarshaling return header; nested exception is: java.io.EOFException“?

目录标题 异常现场分析解决Chat GPT出场一下增大【Build process heap size (Mbytes) 】试试&#x1f64f;增大【Maven->importing->VM options for importer】试试✅Idea的所有配置说明 异常现场 Error unmarshaling return header; nested exception is: java.io.EOFEx…

C++内存管理(区别C语言)深度对比

欢迎来到我的Blog&#xff0c;点击关注哦&#x1f495; 前言 前面已经介绍了类和对象&#xff0c;对C面向对象编程已经有了全面认识&#xff0c;接下来要学习对语言学习比较重要的是对内存的管理。 一、内存的分区 代码区&#xff1a;存放程序的机器指令&#xff0c;通常是可…