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

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...