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

蓝桥杯:七步诗 ← 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/【题目描述】 煮豆燃豆苴&#xff0c;豆在釜中泣。本是同根生&#xff0c;相煎何太急?---曹植 所以&#xff0c;这道题目关乎豆子! 话说赤壁之战结束后&#xff0c;曹操的船舰被刘备烧了&#xff0c;引领军队从华容…...

Vue 如何快速上手

目录 1. Vue 是什么 &#xff08;概念&#xff09; 1.1. Vue 的两种使用方式 1.2. 优点 1.3. 缺点 2. 创建 Vue 实例&#xff0c;初始化渲染 2.1. 步骤&#xff08;核心步骤 4步&#xff09; 2.2. 练习——创建一个Vue实例 3. 插值表达式 {{ }} 3.1. 介绍 3.2. 作用…...

Vue3:组件间通信-provide和inject实现祖先组件与后代组件间直接通信

一、情景说明 我们学习了很多的组件间通信 这里在学习一种&#xff0c;祖先组件与后代组件间通信的技术 这里的后代&#xff0c;可以是多层继承关系&#xff0c;子组件&#xff0c;子子组件&#xff0c;子子子组件等等。 在祖先组件中通过provide配置向后代组件提供数据在后代…...

微信小程序——小程序和页面生命周期详解

小程序的生命周期 小程序的生命周期主要分为以下几个阶段&#xff1a; 创建&#xff08;onLoad&#xff09;&#xff1a; 当小程序启动时&#xff0c;或者从其他页面跳转到当前页面时&#xff0c;会触发 onLoad 生命周期函数。 这个阶段通常用于初始化页面数据&#xff0c;从服…...

android studio中添加module依赖

android常用的三种依赖 库依赖&#xff08;Library dependency&#xff09;&#xff1a;以访问网址的形式将依赖库相应版本下载到本地; 文件依赖&#xff08;File dependency&#xff09;&#xff1a; 将下载下来的依赖库以.jar文件的形式添加依赖. module依赖&#xff08;Modu…...

【.NET全栈】.NET全栈学习路线

一、微软官方C#学习 https://learn.microsoft.com/zh-cn/dotnet/csharp/tour-of-csharp/ C#中的数据类型 二、2021 ASP.NET Core 开发者路线图 GitHub地址&#xff1a;https://github.com/MoienTajik/AspNetCore-Developer-Roadmap/blob/master/ReadMe.zh-Hans.md 三、路线…...

代码随想录阅读笔记-二叉树【二叉搜索树中的搜索】

题目 给定二叉搜索树&#xff08;BST&#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 NULL。 例如&#xff0c; 在上述示例中&#xff0c;如果要找的值是 5&#xff0c;但因为没有节点…...

1、初识drf

drf的学习需要学习者有django基本使用知识。 文章目录 什么是drf&#xff0c;有什么作用CBV是什么初步使用drf 下载以及django创建项目django最小启动内容修改setting修改 url 编写drf视图编辑url测试返回结果 什么是drf&#xff0c;有什么作用 drf(django rest-framework),让…...

速盾:cdn高防御服务器租用有哪些好处

随着互联网的发展&#xff0c;网络安全问题日益突出。攻击者利用各种手段不断对网站进行攻击&#xff0c;给网站的安全运行带来威胁。为了保障网站的正常运行和数据的安全&#xff0c;越来越多的网站开始租用CDN高防御服务器。那么&#xff0c;租用CDN高防御服务器有哪些好处呢…...

【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权限

系列文章目录 【跟小嘉学 Linux 系统架构与开发】一、学习环境的准备与Linux系统介绍 【跟小嘉学 Linux 系统架构与开发】二、Linux发型版介绍与基础常用命令介绍 【跟小嘉学 Linux 系统架构与开发】三、如何查看帮助文档 【跟小嘉学 Linux 系统架构与开发】四、文件和目录的权…...

ubuntu18.04图形界面卡死,鼠标键盘失灵, 通过MAC共享网络给Ubuntu解决!

ubuntu18.04图形界面卡死&#xff0c;鼠标键盘失灵&#xff0c; 通过MAC共享网络给Ubuntu解决&#xff01; 1. 尝试从卡死的图形界面切换到命令行界面2. 进入bios和grub页面3. 更改Grub中的设置&#xff0c;以进入命令行4. 在命令行页面解决图形界面卡死的问题5. Mac共享WI-FI网…...

ESG认证(ESG=环境、社会和治理 Environmental, Social, and Governance)

什么是ESG认证 ESG认证是指根据企业在环境、社会和治理&#xff08;Environmental, Social, and Governance&#xff09;方面的表现而设立的一种评价或评级体系。 环境&#xff08;Environmental&#xff09;&#xff1a;这一维度关注企业如何管理其对环境的影响&#xff0c;包…...

Cesium Viewer 类学习

Viewer提供了创建和控制3D场景所需的所有基本功能&#xff0c;包括加载3D模型、添加图像覆盖物、设置相机位置和方向、处理用户输入等。 构造函数&#xff1a; new Cesium.Viewer(container, options) 是用来创建一个新的 Cesium 视图器&#xff08;Viewer&#xff09;实例的…...

第十四届省赛大学B组(C/C++)子串简写

原题链接&#xff1a;子串简写 程序猿圈子里正在流行一种很新的简写方法&#xff1a; 对于一个字符串&#xff0c;只保留首尾字符&#xff0c;将首尾字符之间的所有字符用这部分的长度代替。 例如 internationalization 简写成 i18n&#xff0c;Kubernetes 简写成 K8s&#…...

深入浅出 -- 系统架构之微服务架构

1.1 微服务的架构特征&#xff1a; 单一职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责 自治&#xff1a;团队独立、技术独立、数据独立&#xff0c;独立部署和交付 面向服务&#xff1a;服务提供统一标准的接口&…...

YoloV8改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图

摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我…...

Python从0到100(十):Python集合介绍及运用

一、集合定义 定义&#xff1a; 由不同元素组成的集合&#xff0c;集合是一组无序排列 可hash值&#xff0c;可作为字典的key。 特性&#xff1a; 集合的目的是将不同的值存放在一起&#xff0c;不同的集合间用来做关系运算&#xff0c;无须纠结于集合中的单个值。 &#xff0…...

实用技巧:如何取消app的截屏禁用

因为我想要在小鹅通App做笔记,但是被小鹅通App禁用截屏了,这真是一个很糟糕的使用体验,虽然可能是为了保护商家权益…… 方法1 可以让商家设置课程可以截屏 方法2 手机root,安装Xposed框架,利用Xposed框架上面的插件我们可以对手机进行高度定制化,而安装Xposed框架的…...

【氮化镓】GaN SP-HEMT的栅极可靠性

概括总结&#xff1a; 本文研究了氮化镓&#xff08;GaN&#xff09;肖特基型p-栅高电子迁移率晶体管&#xff08;GaN SP-HEMT&#xff09;的栅极鲁棒性和可靠性&#xff0c;通过一种新的电路方法评估了在实际转换器中栅极电压&#xff08;VGS&#xff09;过冲波形的栅极电压应…...

Linux基础和进阶用法

Linux是一个广泛使用的开源操作系统&#xff0c;下面是一些Linux基础用法的详细介绍&#xff1a;文件和目录操作&#xff1a;ls&#xff1a;列出文件和目录的详细信息&#xff0c;包括权限、所有者、大小等。cd&#xff1a;切换到指定目录。使用cd ~返回用户主目录&#xff0c;…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...