蓝桥杯:七步诗 ← bfs
【题目来源】
https://www.lanqiao.cn/problems/3447/learning/
【题目描述】
煮豆燃豆苴,豆在釜中泣。本是同根生,相煎何太急?---曹植
所以,这道题目关乎豆子!
话说赤壁之战结束后,曹操的船舰被刘备烧了,引领军队从华容道撤退,路上遇到了泥泞,道路不通畅,又刮起了大风,没办法,只好让羸弱的士兵背着草填在马下,骑兵才能过去。
走着走着,军队路遇—片豆地,由于战马已经饥饿难耐,急需吃些豆子补充体力,这样才能继续行进,但是大家都知道,马儿只会走“日”字,于是问题来了,已知豆地的大小为 n×m(n 行 m 列),每个坐标点上面有散落着的豆子、枯萎的豆萁以及坑洼的湿地,马儿只会吃豆子,不会吃豆萁,且马儿不会走到坑洼的湿地上面,因为湿地会让它深陷其中,无法行动;当然也不能走到 n ×m 豆地范围之外。
为了方便描述,豆子用字母 b 表示,豆萁用字母 q 表示,湿地用字母 x 表示,马儿所在的位置用字母S表示(题目测试数据保证 S 在 n×m 的豆地范围内),现在请你计算—下,马儿最多能吃到豆地里面多少颗豆子,并输出对应的答案。
【输入格式】
输入第 1 行包含两个正整数 n 和 m,表示豆地的大小。
第 2~n+1 行每行包含 m 个字符,表示豆地里面的豆子、豆萁、湿地以及马儿所在的起点位置。
【输出格式】
输出—行,这—行包含一个整数,表示答案。
【样例输入1】
2 3
Sqx
xxx
【输出样例1】
0
【输入样例2】
3 3
bbb
Sqb
bbb
【输出样例2】
7
【说明/提示】
对于所有评测数据,1≤n, m≤400。
【算法分析】
BFS算法助记:建-入-量:头-出-入,详见:
https://blog.csdn.net/hnjzsyjyj/article/details/125801217
【算法代码】
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;const int maxn=404;
int st[maxn][maxn];
int n,m;
int sx,sy;
int dx[]= {-2,-1,1,2,2,1,-1,-2};
int dy[]= {1,2,2,1,-1,-2,-2,-1};queue<PII> Q;
int bfs(int x,int y) {int ans=0;Q.push({x,y});while(Q.size()) {PII t=Q.front();int x=t.first;int y=t.second;Q.pop();for(int i=0; i<8; i++) {int nx=x+dx[i];int ny=y+dy[i];if(nx>=0 && nx<n && ny>=0 && ny<m && (st[nx][ny]==0 || st[nx][ny]==-1)) {if(st[nx][ny]==0) ans++;st[nx][ny]=1;Q.push({nx,ny});}}}return ans;
}int main() {cin>>n>>m;char ch;for(int i=0; i<n; i++) {for(int j=0; j<m; j++) {cin>>ch;if(ch=='b') st[i][j]=0;else if(ch=='q') st[i][j]=-1;else if(ch=='S') sx=i,sy=j;else st[i][j]=1;}}st[sx][sy]=1;cout<<bfs(sx,sy);return 0;
}/*
in1:
2 3
Sqx
xxxout1:
0
---------
in2:
3 3
bbb
Sqb
bbbout2:
7
*/
【参考文献】
https://www.lanqiao.cn/problems/3447/learning
相关文章:
蓝桥杯:七步诗 ← bfs
【题目来源】https://www.lanqiao.cn/problems/3447/learning/【题目描述】 煮豆燃豆苴,豆在釜中泣。本是同根生,相煎何太急?---曹植 所以,这道题目关乎豆子! 话说赤壁之战结束后,曹操的船舰被刘备烧了,引领军队从华容…...
Vue 如何快速上手
目录 1. Vue 是什么 (概念) 1.1. Vue 的两种使用方式 1.2. 优点 1.3. 缺点 2. 创建 Vue 实例,初始化渲染 2.1. 步骤(核心步骤 4步) 2.2. 练习——创建一个Vue实例 3. 插值表达式 {{ }} 3.1. 介绍 3.2. 作用…...
Vue3:组件间通信-provide和inject实现祖先组件与后代组件间直接通信
一、情景说明 我们学习了很多的组件间通信 这里在学习一种,祖先组件与后代组件间通信的技术 这里的后代,可以是多层继承关系,子组件,子子组件,子子子组件等等。 在祖先组件中通过provide配置向后代组件提供数据在后代…...
微信小程序——小程序和页面生命周期详解
小程序的生命周期 小程序的生命周期主要分为以下几个阶段: 创建(onLoad): 当小程序启动时,或者从其他页面跳转到当前页面时,会触发 onLoad 生命周期函数。 这个阶段通常用于初始化页面数据,从服…...
android studio中添加module依赖
android常用的三种依赖 库依赖(Library dependency):以访问网址的形式将依赖库相应版本下载到本地; 文件依赖(File dependency): 将下载下来的依赖库以.jar文件的形式添加依赖. module依赖(Modu…...
【.NET全栈】.NET全栈学习路线
一、微软官方C#学习 https://learn.microsoft.com/zh-cn/dotnet/csharp/tour-of-csharp/ C#中的数据类型 二、2021 ASP.NET Core 开发者路线图 GitHub地址:https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/blob/master/ReadMe.zh-Hans.md 三、路线…...
代码随想录阅读笔记-二叉树【二叉搜索树中的搜索】
题目 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 在上述示例中,如果要找的值是 5,但因为没有节点…...
1、初识drf
drf的学习需要学习者有django基本使用知识。 文章目录 什么是drf,有什么作用CBV是什么初步使用drf 下载以及django创建项目django最小启动内容修改setting修改 url 编写drf视图编辑url测试返回结果 什么是drf,有什么作用 drf(django rest-framework),让…...
速盾:cdn高防御服务器租用有哪些好处
随着互联网的发展,网络安全问题日益突出。攻击者利用各种手段不断对网站进行攻击,给网站的安全运行带来威胁。为了保障网站的正常运行和数据的安全,越来越多的网站开始租用CDN高防御服务器。那么,租用CDN高防御服务器有哪些好处呢…...
【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权限
系列文章目录 【跟小嘉学 Linux 系统架构与开发】一、学习环境的准备与Linux系统介绍 【跟小嘉学 Linux 系统架构与开发】二、Linux发型版介绍与基础常用命令介绍 【跟小嘉学 Linux 系统架构与开发】三、如何查看帮助文档 【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权…...
ubuntu18.04图形界面卡死,鼠标键盘失灵, 通过MAC共享网络给Ubuntu解决!
ubuntu18.04图形界面卡死,鼠标键盘失灵, 通过MAC共享网络给Ubuntu解决! 1. 尝试从卡死的图形界面切换到命令行界面2. 进入bios和grub页面3. 更改Grub中的设置,以进入命令行4. 在命令行页面解决图形界面卡死的问题5. Mac共享WI-FI网…...
ESG认证(ESG=环境、社会和治理 Environmental, Social, and Governance)
什么是ESG认证 ESG认证是指根据企业在环境、社会和治理(Environmental, Social, and Governance)方面的表现而设立的一种评价或评级体系。 环境(Environmental):这一维度关注企业如何管理其对环境的影响,包…...
Cesium Viewer 类学习
Viewer提供了创建和控制3D场景所需的所有基本功能,包括加载3D模型、添加图像覆盖物、设置相机位置和方向、处理用户输入等。 构造函数: new Cesium.Viewer(container, options) 是用来创建一个新的 Cesium 视图器(Viewer)实例的…...
第十四届省赛大学B组(C/C++)子串简写
原题链接:子串简写 程序猿圈子里正在流行一种很新的简写方法: 对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。 例如 internationalization 简写成 i18n,Kubernetes 简写成 K8s&#…...
深入浅出 -- 系统架构之微服务架构
1.1 微服务的架构特征: 单一职责:微服务拆分粒度更小,每一个服务都对应唯一的业务能力,做到单一职责 自治:团队独立、技术独立、数据独立,独立部署和交付 面向服务:服务提供统一标准的接口&…...
YoloV8改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图
摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我…...
Python从0到100(十):Python集合介绍及运用
一、集合定义 定义: 由不同元素组成的集合,集合是一组无序排列 可hash值,可作为字典的key。 特性: 集合的目的是将不同的值存放在一起,不同的集合间用来做关系运算,无须纠结于集合中的单个值。 ࿰…...
实用技巧:如何取消app的截屏禁用
因为我想要在小鹅通App做笔记,但是被小鹅通App禁用截屏了,这真是一个很糟糕的使用体验,虽然可能是为了保护商家权益…… 方法1 可以让商家设置课程可以截屏 方法2 手机root,安装Xposed框架,利用Xposed框架上面的插件我们可以对手机进行高度定制化,而安装Xposed框架的…...
【氮化镓】GaN SP-HEMT的栅极可靠性
概括总结: 本文研究了氮化镓(GaN)肖特基型p-栅高电子迁移率晶体管(GaN SP-HEMT)的栅极鲁棒性和可靠性,通过一种新的电路方法评估了在实际转换器中栅极电压(VGS)过冲波形的栅极电压应…...
Linux基础和进阶用法
Linux是一个广泛使用的开源操作系统,下面是一些Linux基础用法的详细介绍:文件和目录操作:ls:列出文件和目录的详细信息,包括权限、所有者、大小等。cd:切换到指定目录。使用cd ~返回用户主目录,…...
Linux运维-SHELL编程之正则表达式与流编辑处理器
Linux运维-SHELL编程之正则表达式与流编辑处理器 什么是正则表达式 正则表达式是一种用来描述字符序列的强大工具,通常用于字符串的匹配、搜索和替换操作。它由普通字符(例如字母、数字)和特殊字符(称为元字符)组成&…...
openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint
文章目录 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint256.1 功能描述256.2 语法格式256.3 参数说明 openGauss学习笔记-256 openGauss性能调优-使用Plan Hint进行调优-优化器GUC参数的Hint 256.1 功能描述 设置本次查询执行内生效的…...
flex:1的作用是什么?
占满剩余的高度 <div classfather><div classson1></div><div classson2></div> </div>当给father添加display:flex之后,假设给son2添加flex:1,那么son2将会占满除son1之外的高度...
Mysql安装(命令方式安装)
下载mysql压缩包 Mysql可以使用界面安装,也可以使用命令的方式安装,今天我们使用命令的方式安装mysql。首先下载mysql压缩包(下载地址:https://dev.mysql.com/downloads/mysql/),解压到你想要安装的目录。 …...
Vben Admin实战-系统管理之用户管理-(第12节)
系列文章目录 第一节:Vben Admin介绍和初次运行 第二节:Vben Admin 登录逻辑梳理和对接后端准备 第三节:Vben Admin登录对接后端login接口 第四节:Vben Admin登录对接后端getUserInfo接口 第五节:Vben Admin权限-前端控制方式 第六节:Vben Admin权限-后端控制方式 第七节…...
Oracle常规操作
1、查看用户和密码 select username,password from dba_users; --修改用户和密码 alter user system identified by manager; alter user system identified by values 2D594E86F93B17A1; --解锁用户 alter user system account unlock; -- 用SYSDBA身份进入数据库,然…...
「33」如何让你的直播场景增加透视感?
「33」模糊滤镜增强背景画面透视感 在直播中,背景一直是作为一种陪衬而存在的,位于主场景的后面,其实,说得更直白一些,背景的存在就犹如“绿叶”,是为了衬托红花更加艳丽。所以…… 你通过画面背景的调整,可以从整体上对视频或图片的画面进行装饰,有助于增加画面的空间…...
Macbook文件清理软件 Mac电脑清理垃圾文件怎么清理
为了维护Macbook电脑的系统健康,我们需要定期给电脑进行全面清理,清除系统垃圾文件、软件缓存和系统内存。那么好用的Macbook文件清理软件有哪些呢?今天就给大家介绍几款好用的电脑清理软件并介绍Mac电脑清理垃圾文件怎么清理。 一、Macbook…...
【Java基础】Java基础知识整合
文章目录 1. 转义字符2. 变量2.1 字符串与整型相加2.2 byte和short的区别2.3 float和double的区别2.4 char类型2.5 boolean类型2.6 自动类型转换及运算2.7 强制类型转换2.8 String的转换2.9 除法运算2.10 取模规则 3. 自增4. 逻辑运算符5. 赋值运算 6. 三元运算符:7…...
构建集创建、售卖、转让于一体,且基于ERC721 token的NFT平台,从编写智能合约开始(Web3项目四实战之一)
NFT 全称是 non-fungible token(非同质化代币或不可篡改代币)是记录在区块链上的唯一数字标识符,用于证明所有权和真实性。NFT 的所有权记录在区块链中,所有者可以转让,从而允许 NFT 出售和交易。任何人都可以创建 NFT,创建 NFT 几乎不需要任何编码技能。NFT 通常包含对艺…...
网站建设案例简介怎么写/seo优化网站推广全域营销获客公司
Qt安装Windows调试器 1. 打开网址:https://developer.microsoft.com/zh-cn/windows/downloads/windows-10-sdk,选择“下载安装程序”,下载“winsdksetup.exe”; 2. 打开“winsdksetup.exe”,按下述步骤操作ÿ…...
搜索网站做推广/成都seo专家
2019独角兽企业重金招聘Python工程师标准>>> 先上一个简单的例子: /*** window*/var w new Ext.Window({rander : Ext.getBody(),width : 300,height : 200,title : "标题"}); w.show(); 显示的效果如下: 再介绍几个常用的参数&am…...
沈阳室内设计公司排名/seo快速排名优化方式
Hadoop2.7.3 Writable 序列化之二1. Hadoop序列化背景或原因2. Hadoop Writable机制3. 实验内容3.1 思路3.2 编写HadoopPerson类3.3 编写测试类4. 实验结果4.1 调用ser()序列化后文件内容如下4.1 调用反序列化方法deSer()结果如下1. Hadoop序列化背景或原因 Java序列化会附带额…...
南昌模板建站定制/seo方案
从Npm Script到Webpack,6种常见的前端构建工具对比 小编说:历史上先后出现了一系列构建工具,它们各有优缺点。由于前端工程师很熟悉JavaScript,Node.js又可以胜任所有构建需求,所以大多数构建工具都是用Node.js开发的。…...
黄骅港旅游景点大全/厦门关键词优化平台
作者:frank909 https://blog.csdn.net/briblue/article/details/76736356 泛型,一个孤独的守门者。 大家可能会有疑问,我为什么叫做泛型是一个守门者。这其实是我个人的看法而已,我的意思是说泛型没有其看起来那么深不可测&#…...
永州网站开发公司/疫情最新资讯
AudioTrack可以读取网络上面的,这个需要后面去添加,涉及的东西太多了, 现在看看AudioRecord,查看API : http://developer.android.com/reference/android/media/AudioRecord.html <1> : AudioRecord构造函数: public AudioRecord (int audioSource, int sampleRateInHz,…...