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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...