【洛谷刷题】蓝桥杯专题突破-深度优先搜索-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 配置镜像加…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...