当前位置: 首页 > 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…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

[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…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...