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

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

目录

写在前面:

题目:P1683 入门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

输出格式:

输入样例:

输出样例:

解题思路:

代码:

AC !!!!!!!!!!

写在最后:


写在前面:

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

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

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

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

题目:P1683 入门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:

输入格式:

第一行两个正整数 W 和 H,分别表示小路的宽度和长度。

以下 H 行为一个 H × W 的字符矩阵。每一个字符代表一块瓷砖。

其中,. 代表安全的砖,# 代表不安全的砖,@ 代表第一块砖。

输出格式:

输出一行,只包括一个数,

即你从第一块砖开始所能安全走过的最多的砖块个数(包括第一块砖)。

输入样例:

11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

输出样例:

59

解题思路:

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

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

因为我们要保证,

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

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

 接下来是具体思路

这道题的思路就是:

1. 先遍历所有位置找到起始的点位,

2. 然后以那个点位@为起点,向上下左右四个方向搜索,

3. 搜索一次记一次数,将搜索的位置标记以防重复搜索,

继续搜索:

4. 搜索完所有位置之后就返回记录的数即可。

那么下面是代码实现:

代码:

//包常用头文件
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int n, m;const int N = 30;//用一个二维数组接收地图
char g[N][N];//计数
int res = 0;//记录偏移量
int q[] = {1, 0, -1, 0};
int w[] = {0, 1, 0, -1};void dfs(int x, int y)
{//四个方位搜索for(int i = 0; i < 4; i++){int a = x + q[i];int b = y + w[i];//如果到边界了,就不搜索if(a < 0 || b < 0 || a >= n || b >= m) continue;//如果不是'.'就不搜索if(g[a][b] != '.') continue;//搜索完就标记g[a][b] = '#';res++;dfs(a, b);}
}int main()
{scanf("%d %d", &m, &n);//接收地图for(int i = 0; i < n; i++){scanf("%s", g[i]);}//遍历地图,找到@for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(g[i][j] == '@'){//@作为第一个位置,res++res++;dfs(i, j);break;//只有一个起始位置,找到就直接出来}}}printf("%d", res);return 0;
}

AC !!!!!!!!!!

写在最后:

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

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

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

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

相关文章:

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

目录 写在前面&#xff1a; 题目&#xff1a;P1683 入门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; 代码&#xff1a; AC &a…...

论文解读TCPN

一、简要介绍视觉信息提取&#xff08;VIE&#xff09;近年来受到了越来越多的关注。现有的方法通常首先将光学字符识别&#xff08;OCR&#xff09;结果组织成纯文本&#xff0c;然后利用标记级实体注释作为监督来训练序列标记模型。但是&#xff0c;它花费大量的注释成本&…...

性能优化之防抖与节流

&#xff08;一&#xff09;防抖 &#xff08;1&#xff09;定义&#xff1a;单位事件内&#xff0c;频繁触发&#xff0c;只执行最后一次&#xff08;像王者荣耀的回城操作&#xff09; &#xff08;2&#xff09;使用场景&#xff1a;搜索输入框、手机号邮箱输入检测 &…...

数组模拟单链表

实现一个单链表&#xff0c;链表初始为空&#xff0c;支持三种操作&#xff1a; 向链表头插入一个数&#xff1b; 删除第 k个插入的数后面的数&#xff1b; 在第 k个插入的数后插入一个数。 现在要对该链表进行 M次操作&#xff0c;进行完所有操作后&#xff0c;从头到尾输出整…...

蓝桥杯刷题第十四天

第二题&#xff1a;不同子串题目描述本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如&#xff0c;字符串aaab 有非空子串 a, b, aa, ab, aaa, aa…...

面试了8家软件公司测试岗位,面试题大盘点,我真的尽力了

包含的模块&#xff1a;本文分为十九个模块&#xff0c;分别是&#xff1a;软件测试 基础、liunx、MySQL、web测试、接口测试、APP测试 、管理工具、Python、性能测试、selenium、lordrunner、计算机网络、组成原理、数据结构与算法、逻辑题、人力资源需要的可以看文末获取方式…...

Activiti 工作流简介

1、什么是工作流 工作流(Workflow)&#xff0c;就是通过计算机对业务流程自动化执行管理。它主要解决的是“使在多个参与者之间按照某种预定义的规则自动进行传递文档、信息或任务的过程&#xff0c;从而实现某个预期的业务目标&#xff0c;或者促使此目标的实现”。 1.2、工作…...

【华为机试真题详解 Python实现】统计差异值大于相似值二元组个数【2023 Q1 | 100分】

文章目录 前言题目描述输入描述输出描述题目解析参考代码前言 《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即非性能最优)…...

【C++】Google编码风格学习

Google规范线上地址&#xff1a;https://zh-google-styleguide.readthedocs.io/en/latest/ 文章目录1. 头文件2. 作用域3. 类4. 函数5. 其他C特性6. 命名约定7. 注释8. 格式1. 头文件 每个cpp/cc文件都对应一个h头文件&#xff0c;除单元测试代码和只包含main()的文件外。 所…...

JavaScript 中的Promise 函数

JavaScript 中的Promise 函数 目录JavaScript 中的Promise 函数1 创建Promise2 Promise的方法3 Promises的状态4 Promise的使用5 返回 Promise 类型6 Promise级联使用在现在的前端开发中我们常常会使用到 JavaScript Promise 函数&#xff0c;但是很多人都不能正确理解Promise …...

学校教的Python,找工作没企业要,太崩溃了【大四真实求职经历】

如果只靠学校学的东西去找工作&#xff0c;能找到工作吗&#xff1f; 今天给大家看一个粉丝的真实求职案例&#xff0c;想做Python方面的工作&#xff0c;投了二十几个简历却没人要&#xff0c;心态崩了。为什么没人要&#xff1f;我来告诉你答案。 然后我还会结合我的这些年的…...

快看!这只猫两次登上 Github Trending !!!

前几天我在逛 Github Trending&#xff0c;无意间发现这个Postcat 登上榜单 !好奇心驱使我去了解这个 Postcat。近期它上新了几个有意思的插件&#xff0c;其中 ChatGPT 插件&#xff0c;用户可以直接省去复杂的流程&#xff0c;直接体验 ChatGPT&#xff0c;懂的都懂&#xff…...

Linux->文件系统初识

目录 前言&#xff1a; 1 认识文件 2 文件使用 2.1 文件加载 2.2 外设文件使用 3 文件接口和文件描述符 3.1 文件系统调用接口 open&#xff1a; 3.2 文件描述符 4 缓冲区 前言&#xff1a; 在大家看这篇文章之前&#xff0c;我得提出几个问题&#xff1a; 1. 我们有多…...

InfluxDB和IotDB介绍与性能对比

InfluxDB简介 InfluxDB 是用Go语言编写的一个开源分布式时序、事件和指标数据库&#xff0c;无需外部依赖。用于存储和分析时间序列数据的开源数据库。 适合存储设备性能、日志、物联网传感器等带时间戳的数据,其设计目标是实现分布式和水平伸缩扩展。 InfluxDB 包括用于存储和…...

计算机体系结构(校验码+总线)

校验码计算机系统运行时&#xff0c;为了确保数据在传送过程中正确无误&#xff0c;一是提高硬件电路的可靠性&#xff1b;二就是是提高代码的校验能力&#xff0c;包括查错和纠错。通常使用校验码的方法检测传送的数据是否出错。这里的校验码主要是指循环冗余校验码&#xff0…...

JavaWeb《三》Request请求转发与Response响应

&#x1f34e;道阻且长&#xff0c;行则将至。&#x1f353; 本文是javaweb的第三篇&#xff0c;介绍了Request请求转发与Response响应。 上一篇&#xff1a;JavaWeb《二》Servlet、Request请求 下一篇&#xff1a;敬请期待 目录一、Request请求转发&#x1f34f;二、Response对…...

断言assert

assert作用&#xff1a;我们使用assert这个宏来调试代码语法&#xff1a;assert&#xff08;bool表达式&#xff09;如果表达式为false&#xff0c;会调用std::cout<<abort函数&#xff0c;弹出对话框&#xff0c;#include<iostream> #include<cassert> void…...

【Java项目】完善基于Java+MySQL+Tomcat+maven+Servlet的博客系统

目录一、准备工作二、引入依赖三、创建必要的目录四、编写代码五/六、打包部署(直接基于 smart tomcat)七、验证代码正式编写服务器代码编写数据库相关的操作代码创建数据库/表结构(数据库设计)数据库代码封装数据库操作封装针对数据的增删改查&#xff01;博客列表页约定前后端…...

详解结构体内存对齐

目录 前言 一、内存大小的计算 1.规则 2.练习 二、为什么要有内存对齐 1.移植原因 2.性能原因 三、修改默认对齐数 总结 前言 本文针对结构体大小的计算进行深度剖析。结构体的大小要遵守内存对齐&#xff0c;在绝大数情况下&#xff0c;会浪费空间。但是有其的价值&…...

指针:程序员的望远镜

指针&#xff1a;程序员的望远镜一、什么是指针1.1 指针的定义1.2 指针和普通变量的区别1.3 指针的作用1.4 指针的优点和缺点二、指针的基本操作2.1 取地址运算符"&"2.2 指针的声明与定义2.3 指针的初始化2.4 指针的解引用2.5 指针的赋值2.6 指针的运算2.7 指针的…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

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

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

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...