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

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(7)

目录

写在前面:

题目:P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

输出格式:

输入样例:

输出样例:

解题思路:

代码:

AC !!!!!!!!!!

写在最后:


写在前面:

怎么样才能学好一个算法?

我个人认为,系统性的刷题尤为重要,

所以,为了学好深度优先搜索,为了用好暴搜应对蓝桥杯,

事不宜迟,我们即刻开始刷题!

题目:P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

输入第 11 行:两个空格隔开的整数:N 和 M。

第 22 行到第 N + 1 行:每行 M 个字符,每个字符是 W 或 .

它们表示网格图中的一排。字符之间没有空格。

输出格式:

输出一行,表示水坑的数量。

输入样例:

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出样例:

3

解题思路:

我们使用深度优先搜索的时候,

第一个要注意的点是搜索的顺序,

因为我们要保证,

我们写出的递归结构能够遍历所有情况。

(以上递归搜索的基本思路,多熟悉总是好的)

 接下来是具体思路

1. 遍历整个地图,只要遇到W就开始搜索,

2. 根据题目要求,雨水会从八个方向往外流,那就搜索八个方向,

继续搜索:

3. 被搜索过的地方就标记一下,防止重复搜索,

4. 搜索完一块区域就继续遍历找W,以此类推,返回水坑数量即可。

下面是代码实现: 

代码:

//包常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n, m;//计数
int res = 0;const int N = 110;char g[N][N];//存放偏移量
int st1[] = {1, 1, 1, 0, 0, -1, -1, -1};
int st2[] = {1, 0, -1, 1, -1, 1, 0, -1};void dfs(int x, int y)
{for(int i = 0; i < 8; i++){int a = x + st1[i];int b = y + st2[i];//遇到边界就不往下搜if(a < 0 || a >= n || b < 0 || b >= m) continue;//遇到不是W就不往下搜if(g[a][b] != 'W') continue;//标记g[a][b] = '.';dfs(a, b);}
}int main()
{scanf("%d %d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", g[i]);}//遍历地图找Wfor(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(g[i][j] == 'W'){//计数res++;dfs(i, j);}}}printf("%d", res);return 0;
}

AC !!!!!!!!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关文章:

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(7)

目录 写在前面&#xff1a; 题目&#xff1a;P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; …...

Python嵌套函数(Nested function)和闭包(closure)

Python嵌套函数&#xff08;Nested function&#xff09;和闭包&#xff08;closure&#xff09; 闭包&#xff08;closure&#xff09;是建立在嵌套函数基础上的&#xff0c;是一种特殊的嵌套函数结构。 先看嵌套函数&#xff08;Nested function&#xff09;。 Python允许…...

【实战】React 必会第三方插件 —— Cron 表达式生成器(qnn-react-cron)

文章目录一、引子二、配置使用1.安装2.使用&#xff08;1&#xff09;直接调用&#xff08;2&#xff09;赋值到表单&#xff08;Form&#xff09;&#xff08;3&#xff09;自定义功能按钮&#xff08;4&#xff09;隐藏指定 Tab&#xff08;5&#xff09;其他三、常见问题及解…...

C# 教你如何终止Task线程

我们在多线程中通常使用一个bool IsExit类似的代码来控制是否线程的运行与终止&#xff0c;其实使用CancellationTokenSource来进行控制更为好用&#xff0c;下面我们将介绍CancellationTokenSource相关用法。C# 使用 CancellationTokenSource 终止线程使用CancellationTokenSo…...

整合SpringCache

整合SpringCache 1、引入依赖cache还有redis <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-cache</artifactId> </dependency>2、写配置 spring:cache:type: redis3、测试使用缓存 Cache…...

05 - 环境变量编程

---- 整理自狄泰软件唐佐林老师课程 查看所有文章链接&#xff1a;&#xff08;更新中&#xff09;Linux系统编程训练营 - 目录 文章目录1. 初识环境变量1.1 问题1.2 main函数&#xff08;默认进程入口&#xff09;1.3 什么是环境变量&#xff1f;1.4 环境表的构成1.5 思考2. 深…...

vue3后台管理系统

后面可参考下&#xff1a;vue系列&#xff08;三&#xff09;——手把手教你搭建一个vue3管理后台基础模板 以下代码项目gitee地址 文章目录1. 初始化前端项目初始化项目添加加载效果配置 vite.config.js2. 使用路由安装路由配置路由配置别名和跳转安装pathvite.config.jsjsco…...

掷骰子式的乐趣:探究C语言生成随机数的奥秘

掷骰子式的乐趣&#xff1a;探究C语言生成随机数的奥秘一、引言二、C标准库的rand函数三、srand函数的使用四、基于时间的种子生成五、高质量随机数的应用一、引言 C语言中生成随机数是一项非常重要的功能&#xff0c;因为许多现代应用程序需要使用随机数。随机数可以用于密码…...

一线大厂软件测试常见面试题1500问,背完直接拿捏面试官,

三、测试理论 3.1 你们原来项目的测试流程是怎么样的? 我们的测试流程主要有三个阶段&#xff1a;需求了解分析、测试准备、测试执行。 1、需求了解分析阶段 我们的SE会把需求文档给我们自己先去了解一到两天这样&#xff0c;之后我们会有一个需求澄清会议&#xff0c; 我…...

小迪安全day12WEB漏洞-SQL注入之简要SQL注入

小迪安全day12WEB漏洞-SQL注入之简要SQL注入 注入产生原理详细分析 可控变量带入数据库查询变量未存在过滤或过滤不严谨 连接符区分 and是sql语句连接符&#xff0c;&是uel参数连接符 and 11是注入语句&#xff0c; &是添加一个新变量 数据库内容 数据库A 网站…...

自动化测试学习(七)-正则表达式,你真的会用吗?

目录 一、正则表达式在python中如何使用 二、用正则表达式匹配更多模式 三、常用字符分类的缩写代码 总结 所谓正则表达式&#xff08;regex&#xff09;&#xff0c;就是一种模式匹配&#xff0c;学会用正则匹配&#xff0c;就可以达到事半功倍的效果。 一、正则表达式在…...

验证码——vue中后端返回的图片流如何显示

目录 前言 一、p调用接口获取验证码 canvas画布渲染&#xff1f; 二、后端返回图片&#xff08;图片流&#xff09;&#xff0c;前端显示 1.blob 2.arraybuffer 总结 前言 登录界面经常会有验证码&#xff0c;验证码的实现方式也有很多&#xff0c;我目前做过以下两种&…...

聚观早报 | 拼多多驳斥Google的指控;80%美国人工作将被AI影响

今日要闻&#xff1a;拼多多驳斥Google“恶意软件”的指控&#xff1b;80%美国人工作将被AI影响&#xff1b;iPhone 15 Pro设计图上热搜&#xff1b;贾扬清离职阿里投身AI大模型创业&#xff1b;OPPO Find X6 系列发布拼多多驳斥Google“恶意软件”的指控 3 月 21 日&#xff0…...

define,typedef,inline 的区别

define 1.用于在代码中创建宏定义&#xff0c;将一个标识符替换为一个表达式或语句。例如&#xff1a; #define PI 3.14159 #define SQUARE(x) ((x) * (x))这样&#xff0c;程序中所有出现的 PI 都将被替换为 3.14159&#xff0c;SQUARE(x) 则被替换成了 (x) * (x)。 使用 #…...

百度文心一言正式亮相

OpenAI 刚发布了 GPT-4&#xff0c;百度预热已久的人工智能生成式对话产品也终于亮相了。昨天下午&#xff0c;文心一言 (ERNIE Bot)—— 百度全新一代知识增强大语言模型、文心大模型家族的新成员&#xff0c;正式在百度总部 “挥手点江山” 会议室里发布。 发布会一开场&…...

使用Android架构模板

使用Android架构模板 项目介绍 为了方便开发者引入最新的Android架构组建进行开发&#xff0c;Google官方给我们引入了一个架构模板&#xff0c;方便我们快速进入开发。 github地址&#xff1a; https://github.com/android/architecture-templates 该模板遵循官方架构指南 …...

2023年天津市逆向re2.exe解析-比较难(超详细)

2023年天津市逆向re2.exe解析(较难) 1.拖进IDA里进行分析2.动态调试3.编写EXP脚本获取FLAG4.获得FLAG1.拖进IDA里进行分析 进入主程序查看伪代码 发现一个循环,根据行为初步判定为遍历输入的字符并对其ascii^7进行加密 初步判断sub_1400ab4ec为比较输入和flag的函数 跟进u…...

springboot: mybatis动态拼接sql查询条件

目录 需求01: 根据不同类型 查询不同的订单名, 1. 书写订单 类型转换方法 2. 使用方式: 3.. 构建条件构造器并进行查询, 传递查询参数 4. Mapper 写法 5. 最核心位置 xml位置 6. sql执行效果: 需求01: 根据不同类型 查询不同的订单名, 条件也是不同的, 需要复用sql…...

最优化算法 - 动态规划算法

动态规划算法简介 动态规划&#xff08;Dynamic programming&#xff09;是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的&#xff0c;通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题…...

springCloud学习【3】之Docker(1)

文章目录一 Docker环境准备1.1 应用部署的环境问题1.2 Docker简介1.3 Docker解决操作系统环境差异1.4 Docker和虚拟机的区别1.5 Docker架构1.5.1 镜像和容器1.5.2 DockerHub1.5.3 Docker架构1.5.4 Docker工作流1.6 Docker的安装和启动1.7 安装步骤1.8 启动Docker1.9 配置镜像加…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

JVM垃圾回收机制全解析

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

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

python读取SQLite表个并生成pdf文件

代码用于创建含50列的SQLite数据库并插入500行随机浮点数据&#xff0c;随后读取数据&#xff0c;通过ReportLab生成横向PDF表格&#xff0c;包含格式化&#xff08;两位小数&#xff09;及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...

职坐标物联网全栈开发全流程解析

物联网全栈开发涵盖从物理设备到上层应用的完整技术链路&#xff0c;其核心流程可归纳为四大模块&#xff1a;感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性&#xff0c;例如传感器选型需平衡精度与…...