代码随想录 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…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
