拯救行动(BFS)
公主被恶人抓走,被关押在牢房的某个地方。牢房用 N \times M (N, M \le 200)N×M(N,M≤200) 的矩阵来表示。矩阵中的每项可以代表道路(@)、墙壁(#)、和守卫(x)。
英勇的骑士(r)决定孤身一人去拯救公主(a)。我们假设拯救成功的表示是 "骑士到达了公主所在的位置"。由于在通往公主所在位置的道路中可能遇到守卫,骑士一旦遇到守卫,必须杀死守卫才能继续前进。
现假设骑士可以向上、下、左、右四个方向移动,每移动一个位置需要 11 个单位时间,杀死一个守卫需要花费额外的 11 个单位时间。同时假设骑士足够强壮,有能力杀死所有的守卫。
给定牢房矩阵,公主、骑士和守卫在矩阵中的位置,请你计算拯救行动成功需要花费最短时间。
输入格式
1、两个整数代表 NN 和 M, (N, M \le 200)M,(N,M≤200).
2、随后 NN 行,每行有 MM 个字符。"@" 代表道路,"a" 代表公主,"r" 代表骑士,"x" 代表守卫, "#" 代表墙壁。
输出格式
如果拯救行动成功,输出一个整数,表示行动的最短时间。
如果不可能成功,输出 "Impossible"。
输入样例1:
7 8 #@#####@ #@a#@@r@ #@@#x@@@ @@#@@#@# #@@@##@@ @#@@@@@@ @@@@@@@@输出样例1:
13输入样例2:
13 40 @x@@##x@#x@x#xxxx##@#x@x@@#x#@#x#@@x@#@x xx###x@x#@@##xx@@@#@x@@#x@xxx@@#x@#x@@x@ #@x#@x#x#@@##@@x#@xx#xxx@@x##@@@#@x@@x@x @##x@@@x#xx#@@#xxxx#@@x@x@#@x@@@x@#@#x@# @#xxxxx##@@x##x@xxx@@#x@x####@@@x#x##@#@ #xxx#@#x##xxxx@@#xx@@@x@xxx#@#xxx@x##### #x@xxxx#@x@@@@##@x#xx#xxx@#xx#@#####x#@x xx##@#@x##x##x#@x#@a#xx@##@#@##xx@#@@x@x x#x#@x@#x#@##@xrx@x#xxxx@##x##xx#@#x@xx@ #x@@#@###x##x@x#@@#@@x@x@@xx@@@@##@@x@@x x#xx@x###@xxx#@#x#@@###@#@##@x#@x@#@@#@@ #@#x@x#x#x###@x@@xxx####x@x##@x####xx#@x #x#@x#x######@@#x@#xxxx#xx@@@#xx#x#####@输出样例2:
7
解题思路:因为要求到达‘a'的最小值,所以求每一步时都用前一步的最小值来求,那么就需要使用优先队列来做了。
参考答案:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N=2005;
typedef pair<int,int> PII;
char a[N][N];
int n,m,sx,sy,dist[N][N];
struct node{int x,y,s;friend bool operator<(node a,node b){return a.s>b.s;}
}cur,nex;
bool st[N][N];
priority_queue<node> q;
void BFS()
{st[sx][sy]=true;cur={sx,sy,0};q.push(cur);int ne[4][2]={{0,1},{0,-1},{1,0},{-1,0}};while(q.size()){auto it=q.top();q.pop();int x=it.x,y=it.y, s=it.s;for(int i=0;i<=3;i++){int tx=x+ne[i][0],ty=y+ne[i][1];if(a[tx][ty]=='a'){cout<<s+1;return ;}if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]!='#'&&!st[tx][ty]){st[tx][ty]=true;if(a[tx][ty]=='x'){cur={tx,ty,s+2};q.push(cur);}if(a[tx][ty]=='@'){cur={tx,ty,s+1};q.push(cur);}}}}cout<<"Impossible";
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++){cin>>a[i][j];if(a[i][j]=='r') sx=i,sy=j;} BFS();return 0;
}
相关文章:
拯救行动(BFS)
公主被恶人抓走,被关押在牢房的某个地方。牢房用 N \times M (N, M \le 200)NM(N,M≤200) 的矩阵来表示。矩阵中的每项可以代表道路()、墙壁(#)、和守卫(x)。 英勇的骑士(r…...
985硕的4家大厂实习与校招经历专题分享(part2)
我的个人经历: 985硕士24届毕业生,实验室方向:CV深度学习 就业:工程-java后端 关注大模型相关技术发展 校招offer: 阿里巴巴 字节跳动 等10 研究生期间独立发了一篇二区SCI 实习经历:字节 阿里 京东 B站 (只看大厂,面试…...
【NR技术】 3GPP支持无人机的关键技术以及场景
1 背景 人们对使用蜂窝连接来支持无人机系统(UAS)的兴趣浓厚,3GPP生态系统为UAS的运行提供了极好的好处。无处不在的覆盖范围、高可靠性和QoS、强大的安全性和无缝移动性是支持UAS指挥和控制功能的关键因素。与此同时,监管机构正在调查安全和性能标准以及…...
【译】WordPress Bricks主题安全漏洞曝光,25,000个安装受影响
WordPress的Bricks主题存在一个严重的安全漏洞,恶意威胁行为者正在积极利用该漏洞在易受攻击的安装上运行任意PHP代码。 该漏洞被跟踪为CVE-2024-25600(CVSS评分:9.8),使未经身份验证的攻击者能够实现远程代码执行。它…...
【C++ 23种设计模式】
C 23种设计模式 ■ 创建型模式(5种)■ 工厂模式■ 抽象工厂模式■ 原型模式■ 单例模式■ 第一种:单线程(懒汉)■ 第二种:多线程(互斥量实现锁懒汉)■ 第三种:多线程(const static饿…...
亚信安慧AntDB:企业数据管理的明日之星
在信息科技飞速发展的时代,亚信科技AntDB团队提出了一项颠覆性的“超融合”理念,旨在满足企业日益增长的复杂混合负载和多样化数据类型的业务需求。这一创新性框架的核心思想在于融合多引擎和多能力,充分发挥分布式数据库引擎的架构优势&…...
Android Gradle开发与应用 (三) : Groovy语法概念与闭包
1. Groovy介绍 Groovy是一种基于Java平台的动态编程语言,与Java是完全兼容,除此之外有很多的语法糖来方便我们开发。Groovy代码能够直接运行在Java虚拟机(JVM)上,也可以被编译成Java字节码文件。 以下是Groovy的一些…...
Android 14 设置锁屏为NONE后开启双卡PIN锁,重启设备后,输完卡1的PIN码就进入了安卓界面,未提示输入卡2的PIN码
一.问题背景 目前在多个Android14平台发现开启双卡PIN码并且关闭屏幕锁的情况下,第二个PIN码锁输入弹框不能弹出问题,导致第二个卡不能注网。 如下是未修改前重启后解锁卡1PIN码的状态 可以看出卡2不能正常使用 二.何处关闭了卡2的PIN锁? 1.添加日志 首先在KeyguardSecu…...
2024 GoLand激活,分享几个GoLand激活的方案
文章目录 GoLand公司简介我这边使用GoLand的理由GoLand 最新变化GoLand 2023.3 最新变化AI Assistant 正式版GoLand 中的 AI Assistant:_Rename_(重命名)GoLand 中的 AI Assistant:_Write documentation_(编写文档&…...
linux中对信号的认识
信号的概念与相关知识认识 信号是向目标进程发送消息通知的的一种机制。 信号可以以异步的方式发送给进程,也就是说,进程无需主动等待,而是在任何时间都可以接收到信号。 信号的种类 用kill-l命令查看系统定义的信号列表: 前台…...
【万题详解】P1048 [NOIP2005 普及组] 采药
题目描述 链接——题目在这里!!! 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草…...
Golang基于Redis bitmap实现布隆过滤器(完结版)
Golang基于Redis bitmap实现布隆过滤器(完结版) 为了防止黑客恶意刷接口(请求压根不存在的数据),目前通常有以下几种做法: 限制IP(限流)Redis缓存不存在的key布隆过滤器挡在Redis前 …...
Java基础-内部类
内部类 引言内部类的共性成员内部类静态内部类非静态内部类 局部内部类匿名内部类内部类的使用场景和好处 引言 Java不仅可以定义变量和方法,还可以定义类. 内部类允许你把一些逻辑相关的类组织在一起,并可以控制内部中类的可见性. 这么看来,内部类就像是代码一种隐藏机制:将类…...
设计模式-行为型模式-职责链模式
在软件系统运行时,对象并不是孤立存在的,它们可以通过相互通信协作完成某些功能,一个对象在运行时也将影响到其他对象的运行。行为型模式(Behavioral Pattern)关注系统中对象之间的交互,研究系统在运行时对…...
代码随想录算法训练营第四十天|LeetCode343 整数拆分、LeetCode96 不同的二叉搜索树
343.整数拆分 思路:确定dp数组以及下标的含义 dp[i]代表 i可以被拆分后的最大乘积。确定递推公式,假如拆成连个数,dp[i] j*(i-j),拆成两个数以上,dp[i]j*dp[i-j],j的范围为1到i-1.dp[i]找到所有情况的最大值。初始化…...
接口自动化测试用例如何设计
说到自动化测试,或者说接口自动化测试,多数人的第一反应是该用什么工具,比如:Python Requests、Java HttpClient、Apifox、MeterSphere、自研的自动化平台等。大家似乎更关注的是哪个工具更优秀,甚至出现“ 做平台的 &…...
弱电综合布线:连接现代生活的纽带
在当今信息化快速发展的时代,弱电网络布线作为信息传输的重要基础设施,其作用日益凸显。它不仅保障了数据的高效流通,还确保了通信的稳定性。从商业大厦到教育机构,从政府机关到医院急救中心,再到我们居住的社区&#…...
Java零基础 - 数组的定义和声明
哈喽,各位小伙伴们,你们好呀,我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。 我是一名后…...
CSS补充(下),弹性布局(上)
高级选择器 1.兄弟选择器 2.同时满足 div.bg{background-color: red;}p.bg{background-color: green;}spam.bg{background-color: blue;}注:选择器中间没有空格,有明确标识的选择器写在后面 3.各种伪类的应用 3.1作为第几个子元素 选择器:nth-child…...
图数据库 之 Neo4j - 应用场景4 - 反洗钱(9)
原理 Neo4j图数据库可以用于构建和分析数据之间的关系。它使用节点和关系来表示数据,并提供实时查询能力。通过使用Neo4j,可以将大量的交易数据导入图数据库,并通过查询和分析图结构来发现洗钱行为中的模式和关联。 案例分析 假设有一家转账服务公司,有以下交易数据,每个…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
