蓝桥杯:七步诗 ← 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 ~返回用户主目录,…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...