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

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;
}

相关文章:

dfs,CF 196B - Infinite Maze

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 https://codeforces.com/problemset/problem/196/B 二、解题报告 1、思路分析 考虑如何判断一条路径可以无限走&#xff1f; 我们对朴素的网格dfs改进&#xff0c;改进为可以dfs网格外的区域 如果存在某个…...

鸿蒙应用框架开发【JS注入与执行】 Web

JS注入与执行 介绍 本示例基于H5游戏&#xff0c;通过arkui的button实现对游戏实现基本控制&#xff0c;展示webview的JS注入与执行能力&#xff0c;及native应用与H5的通信能力。 效果预览 使用说明 1.设备连接热点&#xff0c;可访问互联网。 2.打开应用&#xff0c;通过…...

AI问答:理解 DRG / Diagnosis Related Group / 按疾病诊断相关分组

DRG&#xff08;Diagnosis Related Group&#xff09;系统&#xff0c;中文译作“按疾病诊断相关分组”&#xff0c;是一种根据病情临床相似程度和资源消耗水平将住院病人进行分组的系统。以下是对DRG系统的详细理解&#xff1a; 一、定义与原理 1.1、定义&#xff1a;DRG系统…...

多个线程同时调用接口

1、线程的基本概念 线程是程序执行的最小单元。每个线程可以独立执行一段代码&#xff0c;与其他线程并行运行。Java提供Thread类和Runnable接口来创建和管理线程。 2、创建线程 1&#xff09;继承Thread类并重写run()方法&#xff1a; class MyThread extend Thread{ pub…...

本科阶段最后一次竞赛Vlog——2024年智能车大赛智慧医疗组准备全过程——1到手测试

本科阶段最后一次竞赛Vlog——2024年智能车大赛智慧医疗组准备全过程——1到手测试 ​ 大家好&#xff0c;今天给大家带来的是购买到小车或者说RDK X3之后直接快速体验&#xff0c;今天主要围绕官方的快速入门手册进行逐步测试 1.知识补充1 ​ 在这里首先要给新手小白补充几…...

2024第三届钉钉杯大学生大数据挑战赛【A题】完整分享

2024第三届钉钉杯大学生大数据挑战赛已经开赛&#xff0c;小编给大家带来非常实用的助力【A题】完整&#xff0c;&#xff08;看图片下方的说明&#xff09;&#xff0c;资料预览&#xff1a; 微信公众号...

下面关于数组排序的说明那项是错误的?

下面关于数组排序的说明那项是错误的&#xff1f; A. java.util.Arrays类提供有数组排序的支持方法&#xff1a;sort()&#xff1b; B. 通过java.util.Arrays类排序的对象所在类需要实现Comparable或Comparator接口&#xff1b; C. String数组可以进行排序&#xff0c;是因为St…...

【第二篇章】优秀的机器学习策略 超参数优化之决策树

在机器学习的浩瀚星空中&#xff0c;决策树作为一颗璀璨的星辰&#xff0c;以其直观易懂、解释性强以及高效处理分类与回归任务的能力&#xff0c;赢得了众多数据科学家与工程师的青睐。随着大数据时代的到来&#xff0c;如何从海量数据中提炼出有价值的信息&#xff0c;构建出…...

httprunner转载

基于 HttpRunner4.0 的接口自动化测试实践 测试之家 from httprunner import HttpRunner, Config, Step, RunRequest, RunTestCase # 配置数据库连接信息 config ( Config("database test") .variables( **{ "db_host": &…...

反序列化漏洞vulhub靶场serial

环境搭建 下载 https://download.vulnhub.com/serial/serial.zip 解压出来就是这种 你会得到一个这样的文件&#xff0c;这里使用VMware新建一个虚拟机&#xff0c;这里记录比较重要的几部分。 这里就是使用我们刚才下过来的。 漏洞过程详解 1.信息收集 打开靶机&#xff0…...

C++ 文件流详解

在 C 中&#xff0c;文件处理是一个常见且重要的任务。标准库提供了三种主要的文件流类来处理文件输入和输出&#xff1a;fstream、ifstream 和 ofstream。这些类都在 <fstream> 头文件中定义。 一、fstream 类 fstream 是文件流类的基类&#xff0c;既可以用于读操作&…...

docker compse简介与安装

目录 1. Docker Compose 简介 2. Docker Compose 安装 2.1 在 Ubuntu 上安装 Docker Compose 2.1.1 通过 apt 安装 2.1.2 使用官方脚本安装最新版本 2.2 在 CentOS 上安装 Docker Compose 2.2.2 使用官方脚本安装最新版本 2.2.3 使用 pip 安装 2.3 在 openEuler 上安装…...

基于深度学习的零样本学习

零样本学习&#xff08;Zero-Shot Learning, ZSL&#xff09;是深度学习中的一个前沿研究领域&#xff0c;其目标是在没有见过目标类别的样本的情况下&#xff0c;对这些新类别进行识别或分类。这种方法特别适用于在实际应用中存在大量未标注类别或新类别不断涌现的场景&#x…...

C++——list容器以及手动实现

LIST容器 list概述列表容器属性例子 list函数构造函数默认构造函数&#xff1a;带有元素个数和元素初值的构造函数&#xff1a;范围构造函数&#xff1a;拷贝构造函数&#xff1a;移动构造函数&#xff1a;示例 赋值运算符重载拷贝赋值操作符 (1)&#xff1a;移动赋值操作符 (2…...

Win11系统文件资源管理器鼠标右键卡顿解决方法

引用链接&#xff1a; Windows 11文件资源管理器崩溃怎么解决&#xff1f;看看这7个解决办法&#xff01;...

零基础学Python之 第十八讲 文件读写

当你开始学习Python编程时&#xff0c;文件读写是一个非常基础且重要的技能。本篇博客将引导你从零开始学习如何在Python中进行文件读写操作。 1. 打开文件 在Python中&#xff0c;要操作一个文件&#xff0c;首先需要打开它。使用内置的 open() 函数来打开文件&#xff0c;语…...

检索增强生成(RAG):智能内容生成的新纪元

引言 在大 AI 时代&#xff0c;生成式人工智能&#xff08;GenAI&#xff09;模型&#xff0c;尤其是大型语言模型&#xff08;LLM&#xff09;&#xff0c;已经展现出了令人瞩目的能力。然而&#xff0c;这些模型在提供信息的准确、即时、专业、权威等方面仍存在局限。检索增…...

ubuntu2204安装elasticsearch7.17.22

下载安装 wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.17.22-amd64.deb wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.17.22-amd64.deb.sha512 shasum -a 512 -c elasticsearch-7.17.22-amd64.deb.sha512 su…...

介绍Servlet后端中两种接收参数方式req.getAttributer和req.getParameter的区别

数据来源 getParameter&#xff1a;此方法用于获取客户端发送的请求中携带的参数&#xff0c;通常这些参数是通过HTTP GET或POST请求传递的表单数据。例如&#xff0c;用户填写的用户名和密码等输入信息。getAttribute&#xff1a;该方法用来获取在服务器端通过setAttribute方法…...

Delphi FMX安卓Android播放mp3音频内存流

【笔记&#xff1a;安卓开发JavaDelphi FMX】 Delphi FMX跨平台的MediaPlayer无法播放音频数据流只能打开音频文件播放&#xff0c;但有时候需要直接播放内存流数据而无需生成文件&#xff0c;可以通过把内存流转ByteArray再通过Android平台系统原生的MediaDataSource或ParcelF…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

第25节 Node.js 断言测试

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

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...