代码随想录 103. 水流问题
103. 水流问题
#include<bits/stdc++.h>
using namespace std;void dfs(vector<vector<int>>& mp, vector<vector<int>>& visit, int y, int x){if (visit[y][x] == 1) return;visit[y][x] = 1;if (y > 0){if (mp[y][x] <= mp[y - 1][x]){dfs(mp, visit, y - 1, x);}}if (x > 0){if (mp[y][x] <= mp[y][x - 1]){dfs(mp, visit, y, x - 1);}}if (y < mp.size() - 1){if (mp[y][x] <= mp[y + 1][x]){dfs(mp, visit, y + 1, x);}}if (x < mp[0].size() - 1){if (mp[y][x] <= mp[y][x + 1]){dfs(mp, visit, y, x + 1);}}
}int main(){int n, m;cin >> n >> m;vector<vector<int>> mp(n, vector<int>(m, 0));vector<vector<int>> visit1(n, vector<int>(m, 0));vector<vector<int>> visit2(n, vector<int>(m, 0));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> mp[i][j];}}for (int i = 0; i < n; i++){dfs(mp, visit1, i, 0);dfs(mp, visit2, i, m - 1);}for (int i = 0; i < m; i++){dfs(mp, visit1, 0, i);dfs(mp, visit2, n - 1, i);}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (visit1[i][j] == 1 && visit2[i][j] == 1){cout << i << " " << j << "\n";}}}return 0;
}
笔者想出的是随想录中比较暴力的解法,笔者想过对暴力的这种做优化,比如在dfs的遍历过程中对节点做标记,标记节点能到哪一类边界,之后的遍历中将周围节点的判决作为依据,减少计算量,但想了想还是有不妥。因为在遍历中很重要的一步是对遍历的流向做限制,比如先遇到的节点是[0][0],那么之后可以从[0][0]到[0][1],但在进入[0][1]后不能再对[0][0]做访问,这是为了避免遍历陷入无限的循环,但在这题中,相同高度的两类节点间,流向是双向的,也就意味着笔者的优化想法会舍弃掉一种流向,导致潜在的错误,而对这个情况,笔者所能想到的解决方法是只对能流到两类边界的节点做标记,但这样同时也会导致一些点被遍历多次的情况出现。
所以笔者还是看了看更巧妙的逆流而上的解法来写。逆流而上的优势在于,遍历过程中只需要考虑一类边界逆流而上所能到达的范围,不需要考虑双向流向,所以在遍历过程中可以对节点做标记,对已经做标记的节点不需要做操作,在对两类边界都遍历一次后,取两个范围的交集即可,最极端的情况也只需对所有点做2次访问就能确定。
代码随想录 103. 水流问题
相关文章:
代码随想录 103. 水流问题
103. 水流问题 #include<bits/stdc.h> using namespace std;void dfs(vector<vector<int>>& mp, vector<vector<int>>& visit, int y, int x){if (visit[y][x] 1) return;visit[y][x] 1;if (y > 0){if (mp[y][x] < mp[y - 1][x…...
数据结构-排序1
1.排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序…...
Springboot 整合 durid
文章目录 Springboot 整合 druiddruid的优势配置参数使用整合 Druid配置数据源配置参数绑定配置参数配置监控页面配置拦截器 Springboot 整合 druid druid的优势 可以很好的监控 DB 池连接 和 SQL 的执行情况可以给数据库密码加密可以很方便的编写JDBC插件 配置参数 使用 整…...
JVM 系列知识体系全面回顾
经过几个月的努力,JVM 知识体系终于梳理完成了。 很早之前也和小伙伴们分享过 JVM 相关的技术知识,再次感谢大家支持和反馈。 最后再次献上 JVM系列文章合集索引,感兴趣的小伙伴可以点击查看。 JVM系列(一) -什么是虚拟机JVM系列(二) -类的…...
crossover软件如何安装程序 及最新图文案张教程
IT之家 2 月 23 日消息,CodeWeavers 近日发布了 CrossOver 24 版本更新,基于近期发布的 Wine 9.0,不仅兼容更多应用和游戏,还初步支持运行 32 位应用程序。 苹果在 macOS Catalina 系统中移除对 32 位软件的支持之后,在…...
Python爬虫之正则表达式于xpath的使用教学及案例
正则表达式 常用的匹配模式 \d # 匹配任意一个数字 \D # 匹配任意一个非数字 \w # 匹配任意一个单词字符(数字、字母、下划线) \W # 匹配任意一个非单词字符 . # 匹配任意一个字符(除了换行符) [a-z] # 匹配任意一个小写字母 […...
Jenkins打包,发布,部署
一、概念 Jenkins是一个开源的持续集成工具,主要用于自动构建和测试软件项目,以及监控外部任务的运行。与版本管理工具(如SVN,GIT)和构建工具(如Maven,Ant,Gradle)结合使…...
CSS 实现楼梯与小球动画
CSS 实现楼梯与小球动画 效果展示 CSS 知识点 CSS动画使用transform属性使用 页面整体布局 <div class"window"><div class"stair"><span style"--i: 1"></span><span style"--i: 2"></span>…...
sqli-labs less-14post报错注入updatexml
post提交报错注入 闭合方式及注入点 利用hackbar进行注入,构造post语句 unameaaa"passwdbbb&SubmitSubmit 页面报错,根据分析,闭合方式". 确定列数 构造 unameaaa" or 11 # &passwdbbb&SubmitSubmit 确定存在注…...
Python开发环境配置(mac M2)
1. 前言 作为一名程序员,工作中需要使用Python进行编程,甚至因为项目需要还得是不同版本的Python如何手动管理多个版本的Python,如何给Pycharm(IDE)配置对应的interpreter等,都成为一个 “不熟练工” 的难…...
其他:Python语言绘图合集
文章目录 介绍注意导入数据函数模块画图 介绍 python语言的科研绘图合集 注意 This dataset includes the following (All files are preceded by "Marle_et_al_Nature_AirborneFraction_"):- "Datasheet.xlsx": Excel dataset containing all annual a…...
处理 Vue3 中隐藏元素刷新闪烁问题
一、问题说明 页面刷新,原本隐藏的元素会一闪而过。 效果展示: 页面的导航栏通过路由跳转中携带的 meta 参数控制导航栏的 显示/隐藏,但在实践过程中发现,虽然元素隐藏了,但是刷新页面会出现闪烁的问题。 项目源码&…...
【MySQL】数据目录迁移
一、使用场景 使用该方法一般是数据目录所在磁盘不支持扩展,只能通过新加磁盘来扩展数据目录磁盘空间。通常是Windows服务器,或者是Linux服务器的mysql数据目录的磁盘没有使用lvm。 二、准备工作 1. 新磁盘初始化,达到可使用状态 2. 需要自己…...
【项目安全设计】软件系统安全设计规范和标准(doc原件)
1.1安全建设原则 1.2 安全管理体系 1.3 安全管理规范 1.4 数据安全保障措施 1.4.1 数据库安全保障 1.4.2 操作系统安全保障 1.4.3 病毒防治 1.5安全保障措施 1.5.1实名认证保障 1.5.2 接口安全保障 1.5.3 加密传输保障 1.5.4终端安全保障 资料获取:私信或者进主页。…...
INS淡绿色风格人像街拍Lr调色教程,手机滤镜PS+Lightroom预设下载!
调色介绍 INS 淡绿色风格人像街拍通过 Lightroom 调色可以营造出清新、自然、时尚的视觉效果。这种风格以淡绿色为主色调,给人一种宁静、舒适的感觉。 预设信息 调色风格:INS风格预设适合类型:人像,街拍,自拍&#…...
python 实现最小路径和算法
最小路径和算法介绍 最小路径和问题通常指的是在一个网格(如二维数组)中,找到从起点(如左上角)到终点(如右下角)的一条路径,使得路径上经过的元素值之和最小。这类问题可以通过多种…...
Vue3实现动态菜单功能
文章目录 0.效果演示1.搭建Vue3项目1.1 vite 脚手架创建 Vue3 项目1.2 设置文件别名1.3 安装配置 element-plus1.4 安装配置路由2.登录页面3.后台管理页面3.1 搭建后台框架3.2 左侧菜单栏3.3 header 用户信息3.4 主要内容3.5 footer4.配置静态路由5.记录激活菜单5.1 el-menu 绑…...
Qt+VS2019+大恒相机相机回调方式总结
一、前言 大恒驱动安装完成后,在安装目录有SDK调用文档,里面有更详细的调用介绍,此文档对近期做的Demo做一个回顾性总结。 二、调用流程概述 三、针对性内容介绍: 1. 在执行相机操作之前,需要先执行此代码࿱…...
Python库pandas之六
Python库pandas之六 输入/输出read_sql函数应用实列 输入/输出 read_sql 函数 词法:pandas.read_sql(sql, con, index_colNone, coerce_floatTrue, paramsNone, parse_datesNone, columnsNone, chunksizeNone, dtype_backend<no_default>, dtypeNone) rea…...
[C++]使用纯opencv部署yolov11-seg实例分割onnx模型
【算法介绍】 在C中使用纯OpenCV部署YOLOv11-seg进行实例分割是一项具有挑战性的任务,因为YOLOv11通常是用PyTorch等深度学习框架实现的,而OpenCV本身并不直接支持加载和运行PyTorch模型。然而,可以通过一些间接的方法来实现这一目标&#x…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Axios请求超时重发机制
Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式: 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
Cursor AI 账号纯净度维护与高效注册指南
Cursor AI 账号纯净度维护与高效注册指南:解决限制问题的实战方案 风车无限免费邮箱系统网页端使用说明|快速获取邮箱|cursor|windsurf|augment 问题背景 在成功解决 Cursor 环境配置问题后,许多开发者仍面临账号纯净度不足导致的限制问题。无论使用 16…...
claude3.7高阶玩法,生成系统架构图,国内直接使用
文章目录 零、前言一、操作指南操作指导 二、提示词模板三、实战图书管理系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 在线考试系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 四、感受 零、前言 现在很多AI大模型可以…...
