当前位置: 首页 > 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;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 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】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;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代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

实战三:开发网页端界面完成黑白视频转为彩色视频

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