【洛谷刷题】蓝桥杯专题突破-深度优先搜索-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)
目录 写在前面: 题目:P1596 [USACO10OCT]Lake Counting S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: …...

Python嵌套函数(Nested function)和闭包(closure)
Python嵌套函数(Nested function)和闭包(closure) 闭包(closure)是建立在嵌套函数基础上的,是一种特殊的嵌套函数结构。 先看嵌套函数(Nested function)。 Python允许…...

【实战】React 必会第三方插件 —— Cron 表达式生成器(qnn-react-cron)
文章目录一、引子二、配置使用1.安装2.使用(1)直接调用(2)赋值到表单(Form)(3)自定义功能按钮(4)隐藏指定 Tab(5)其他三、常见问题及解…...

C# 教你如何终止Task线程
我们在多线程中通常使用一个bool IsExit类似的代码来控制是否线程的运行与终止,其实使用CancellationTokenSource来进行控制更为好用,下面我们将介绍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 - 环境变量编程
---- 整理自狄泰软件唐佐林老师课程 查看所有文章链接:(更新中)Linux系统编程训练营 - 目录 文章目录1. 初识环境变量1.1 问题1.2 main函数(默认进程入口)1.3 什么是环境变量?1.4 环境表的构成1.5 思考2. 深…...

vue3后台管理系统
后面可参考下:vue系列(三)——手把手教你搭建一个vue3管理后台基础模板 以下代码项目gitee地址 文章目录1. 初始化前端项目初始化项目添加加载效果配置 vite.config.js2. 使用路由安装路由配置路由配置别名和跳转安装pathvite.config.jsjsco…...
掷骰子式的乐趣:探究C语言生成随机数的奥秘
掷骰子式的乐趣:探究C语言生成随机数的奥秘一、引言二、C标准库的rand函数三、srand函数的使用四、基于时间的种子生成五、高质量随机数的应用一、引言 C语言中生成随机数是一项非常重要的功能,因为许多现代应用程序需要使用随机数。随机数可以用于密码…...

一线大厂软件测试常见面试题1500问,背完直接拿捏面试官,
三、测试理论 3.1 你们原来项目的测试流程是怎么样的? 我们的测试流程主要有三个阶段:需求了解分析、测试准备、测试执行。 1、需求了解分析阶段 我们的SE会把需求文档给我们自己先去了解一到两天这样,之后我们会有一个需求澄清会议, 我…...
小迪安全day12WEB漏洞-SQL注入之简要SQL注入
小迪安全day12WEB漏洞-SQL注入之简要SQL注入 注入产生原理详细分析 可控变量带入数据库查询变量未存在过滤或过滤不严谨 连接符区分 and是sql语句连接符,&是uel参数连接符 and 11是注入语句, &是添加一个新变量 数据库内容 数据库A 网站…...

自动化测试学习(七)-正则表达式,你真的会用吗?
目录 一、正则表达式在python中如何使用 二、用正则表达式匹配更多模式 三、常用字符分类的缩写代码 总结 所谓正则表达式(regex),就是一种模式匹配,学会用正则匹配,就可以达到事半功倍的效果。 一、正则表达式在…...
验证码——vue中后端返回的图片流如何显示
目录 前言 一、p调用接口获取验证码 canvas画布渲染? 二、后端返回图片(图片流),前端显示 1.blob 2.arraybuffer 总结 前言 登录界面经常会有验证码,验证码的实现方式也有很多,我目前做过以下两种&…...

聚观早报 | 拼多多驳斥Google的指控;80%美国人工作将被AI影响
今日要闻:拼多多驳斥Google“恶意软件”的指控;80%美国人工作将被AI影响;iPhone 15 Pro设计图上热搜;贾扬清离职阿里投身AI大模型创业;OPPO Find X6 系列发布拼多多驳斥Google“恶意软件”的指控 3 月 21 日࿰…...
define,typedef,inline 的区别
define 1.用于在代码中创建宏定义,将一个标识符替换为一个表达式或语句。例如: #define PI 3.14159 #define SQUARE(x) ((x) * (x))这样,程序中所有出现的 PI 都将被替换为 3.14159,SQUARE(x) 则被替换成了 (x) * (x)。 使用 #…...

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

使用Android架构模板
使用Android架构模板 项目介绍 为了方便开发者引入最新的Android架构组建进行开发,Google官方给我们引入了一个架构模板,方便我们快速进入开发。 github地址: 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…...
最优化算法 - 动态规划算法
动态规划算法简介 动态规划(Dynamic programming)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题…...

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使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

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

Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
python读取SQLite表个并生成pdf文件
代码用于创建含50列的SQLite数据库并插入500行随机浮点数据,随后读取数据,通过ReportLab生成横向PDF表格,包含格式化(两位小数)及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...

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