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

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...