P7775 [COCI2009-2010#2] VUK(bfs)

news/2024/3/29 8:49:59/文章来源:https://blog.csdn.net/m0_74969835/article/details/131984777

解题思路

本题大致可分为以下两个部分:

  1. 预处理矩阵上的每一个点与所有树的最短曼哈顿距离。

  2. 计算出一条使每个点最近距离的最小值最大的最优路径。

这两个部分都可以使用 bfs 来求解。

对于第一部分,我们可以将所有树的位置信息丢进一个队列里,用 bfs 求出每一个点与树的最近的曼哈顿距离。

对于第二部分,我们可以使用优先队列搭配 bfs,优先看那些目前最近距离比较大的点,当走过这个点后,算出在这个点之前的所有点与树的距离的最小值,再与当前的这个点与树的距离求出最小值。

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=510;
struct node{int x,y,p;
};
struct di{int x,y,now;bool operator <(const di& i) const{return i.now>now;}
};
int n,m,sx,sy,ex,ey,mmin=1<<30;
queue<node>q;
priority_queue<di>p;
char ch[N][N];
int mp[N][N],idx[]={0,0,1,-1},idy[]={1,-1,0,0};
bool vis[N][N];
void bfs1(){while(!q.empty()){auto tmp=q.front();int x=tmp.x,y=tmp.y,p=tmp.p;q.pop();for(int i=0;i<4;i++){int xx=x+idx[i];int yy=y+idy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){vis[xx][yy]=true;mp[xx][yy]=p+1;q.push({xx,yy,mp[xx][yy]});}}}
}
void bfs2(){while(!p.empty()){auto tmp=p.top();p.pop();int x=tmp.x,y=tmp.y;if(x==ex&&y==ey){mmin=min(mmin,tmp.now);}for(int i=0;i<4;i++){int xx=x+idx[i];int yy=y+idy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){vis[xx][yy]=true;p.push({xx,yy,min(tmp.now,mp[xx][yy])});}}}
}
void solve() {cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>ch[i][j];if(ch[i][j]=='+'){vis[i][j]=true;q.push({i,j,0});}else if(ch[i][j]=='V') sx=i,sy=j;else if(ch[i][j]=='J') ex=i,ey=j;}bfs1();p.push({sx,sy,mp[sx][sy]});memset(vis,false,sizeof vis);bfs2();cout<<mmin<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int tt=1;//cin>>tt;while(tt--)solve();return 0;
}

over~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_337296.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从C语言到C++_29(红黑树封装set和map)红黑树迭代器的实现

目录 1. set和map中的红黑树 2. 仿函数比较键值对 3. 红黑树迭代器的实现 3.1 迭代器 3.2 迭代器-- 3.3 map的operator[ ] 4. 完整代码 Set.h Map.h RedBlackTree.h Test.cpp 本章完&#xff0c; 1. set和map中的红黑树 前一篇红黑树的源代码&#xff1a; #pragm…

掌握Python的X篇_12_如何使用VS Code调试Python程序

本篇将会介绍如何使用VS Code调试Python程序。 文章目录 1. 什么是调试2. 断点3. 如何启动调试4. 监视窗口5. 单步 1. 什么是调试 我们可以利用VS Code对Python代码进行调试。所谓调试&#xff0c;大家可以理解成有能力将程序进行 “慢动作播放”让我们有机会看到程序一步一步…

Diffusion扩散模型学习2——Stable Diffusion结构解析-以文本生成图像(文生图,txt2img)为例

Diffusion扩散模型学习2——Stable Diffusion结构解析-以文本生成图像&#xff08;文生图&#xff0c;txt2img&#xff09;为例 学习前言源码下载地址网络构建一、什么是Stable Diffusion&#xff08;SD&#xff09;二、Stable Diffusion的组成三、生成流程1、文本编码2、采样流…

JetBrains 为测试自动化打造的强大 IDE-Aqua

QA 和测试工程对现代软件开发必不可少。 在 JetBrains&#xff0c;我们相信使用正确的工具对每项工作都很重要。 对我们来说&#xff0c;为自动化测试开发创建单独的工具是自然而然的事&#xff0c;因为这使我们能够满足多角色软件开发团队的需求。 我们很高兴能够推出 JetBra…

信号的学习笔记二

文章目录 信号捕捉signal信号捕捉sigaction信号集未决信号集和阻塞信号集的工作过程 ![在这里插入图片描述](https://img-blog.csdnimg.cn/b896346af6f1462089779e513a7e237b.png)信号集相关函数sigemptysetsigfillsetsigaddsetsigdelsetsigismember应用 以下函数设置内核信号集…

流数据湖平台Apache Paimon(二)集成 Flink 引擎

文章目录 第2章 集成 Flink 引擎2.1 环境准备2.1.1 安装 Flink2.1.2 上传 jar 包2.1.3 启动 Hadoop2.1.4 启动 sql-client 2.2 Catalog2.2.1 文件系统2.2.2 Hive Catalog2.2.3 sql 初始化文件 2.3 DDL2.3.1 建表2.3.2 修改表 2.4 DML2.4.1 插入数据2.4.2 覆盖数据2.4.3 更新数据…

PHP使用Redis实战实录1:宝塔环境搭建、6379端口配置、Redis服务启动失败解决方案

宝塔环境搭建、6379端口配置、Redis服务启动失败解决方案 前言一、Redis安装部署1.安装Redis2.php安装Redis扩展3.启动Redis 二、避坑指南1.6379端口配置2.Redis服务启动&#xff08;1&#xff09;Redis服务启动失败&#xff08;2&#xff09;Redis启动日志排查&#xff08;3&a…

JS-----数据结构与算法(2)

目录 三. 栈结构 1.认识栈结构 2. 封装栈结构 3. 应用 3-1 十进制转二进制 3-2 进制转换法 四. 队列 1.队列是什么&#xff1f; 2.队列的封装 3. 队列的应用-击鼓传花 4. 双端队列 5.判断是否为回文 三. 栈结构 1.认识栈结构 栈&#xff08;stack&#xff09;又…

7.29训练总结

CodeForces - 1609E 这种使得整个串不包含子串’abc’的题目&#xff0c;发现可以用线段树维护 #include<bits/stdc.h> using namespace std; const int maxn1e55; #define lson now<<1 #define rson now<<1|1 struct seg {int a,b,c;int ab,bc,abc; }tr[m…

2023 年还推荐报计算机专业吗?

计算机科学是一个很好的专业&#xff0c;因为它由各种课程组成&#xff0c;为学生在成熟和新兴专业就业做好准备。以下是一些通常属于计算机科学专业的课程&#xff1a; 基本编程介绍了用于构建和维护数字架构和基础设施的编程语言和标准。 微积分为制定高级计算和设计概念提供…

eclipse 最新版没有navigator视图如何解决

使用project exploere视图可以显示类似navigator视图 1.显示project exploere视图 window---->show view --->project exploere 2.project exploere视图转换为类似navigator视图 第一步&#xff1a;点击视图右上角三个点或者倒三角&#xff0c;点击fiters and custom…

蓝图节点编辑器

打印字符串 第02章 蓝图结构 03 -注释和重新路由_哔哩哔哩_bilibili 第02章 蓝图结构 04 - 变量_哔哩哔哩_bilibili 第03章 蓝图简易门 01 - 箱子碰撞_哔哩哔哩_bilibili 第03章 蓝图简易门 02 - 静态Mesh和箭头_哔哩哔哩_bilibili 第03章 蓝图简易门 03 - 设置相对旋转节点_哔…

rocketmq rsqldb 简单记录

GitHub 地址 https://github.com/alibaba/rsqldb/tree/main&#xff0c;是和目前stream sql化看齐的Rocketmq的sql&#xff0c;类似还有kafka的sqlDB 和flink sql。 目前版本0.2 &#xff0c;主要提供rest模式调用&#xff0c;controller类为public class RsqlController支持的…

6G内存运行Llama2-Chinese-7B-chat模型

6G内存运行Llama2-Chinese-7B-chat模型 Llama2-Chinese中文社区 第一步&#xff1a; 从huggingface下载 Llama2-Chinese-7b-Chat-GGML模型放到本地的某一目录。 第二步&#xff1a; 执行python程序 git clone https://github.com/Rayrtfr/llama2-webui.gitcd llama2-web…

儿童居家健身好伙伴,小莫计数摸高训练器

现在的孩子们的越来越不喜欢运动了&#xff0c;总是爱玩手机游戏&#xff0c;对他们的身体健康非常不好&#xff0c;作为家长&#xff0c;我们希望能够给孩子提供更多的运动机会&#xff0c;有必要每天准备一些能让他们活动活动手脚的小游戏&#xff0c;让他们每天有足够的运动…

Pytorch个人学习记录总结 10

目录 优化器 优化器 官方文档地址&#xff1a;torch.optimhttps://pytorch.org/docs/stable/optim.html Debug过程中查看的grad所在的位置&#xff1a; model --> Protected Atributes --> _modules --> ‘model’ --> Protected Atributes --> _modules -…

【matlab】机器人工具箱快速上手-动力学仿真(代码直接复制可用)

动力学代码&#xff0c;按需修改参数 各关节力矩-关节变量的关系曲线&#xff1a; %%%%%%%%SCARA机器人仿真模型 l[0.457 0.325]; L(1) Link(d,0,a,l(1),alpha,0,standard,qlim,[-130 130]*pi/180);%连杆1 L(2)Link(d,0,a,l(2),alpha,pi,standard,qlim,[-145 145]*pi/180);%连…

小学期笔记——天天酷跑1

文件快照&#xff08;File snapshot&#xff09;通常是指对文件系统中某个特定时间点的文件或文件夹的快照或副本。它记录了文件或文件夹在某一时刻的状态&#xff0c;包括文件的内容、属性、权限、位置等信息。 文件快照通常用于数据备份、恢复和版本控制等目的。通过捕捉文件…

关于c++中虚函数和虚函数表的创建时机问题

以这段代码为例。 #include <iostream>using namespace std;class Parent { public:Parent(){}virtual void func1() {};virtual void func2() {}; };class Child :public Parent { public:Child():n(0),Parent(){cout << "Child()" << endl;}vir…

【网络原理】 (1) (应用层 传输层 UDP协议 TCP协议 TCP协议段格式 TCP内部工作机制 确认应答 超时重传 连接管理)

文章目录 应用层传输层UDP协议TCP协议TCP协议段格式TCP内部工作机制确认应答超时重传 网络原理部分我们主要学习TCP/IP协议栈这里的关键协议(TCP 和 IP),按照四层分别介绍.(物理层,我们不涉及). 应用层 我们需要学会自定义一个应用层协议. 自定义协议的原因? 当前的软件(应用…