POJ 3669(优先队列BFS)(对地图进行优化)

2024-04-23 21:08

本文主要是介绍POJ 3669(优先队列BFS)(对地图进行优化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目新颖,解法也是比较难想的。

题目:

Bessie听说有场史无前例的流星雨即将来临;有谶言:陨星将落,徒留灰烬。为保生机,她誓将找寻安全之所(永避星坠之地)。目前她正在平面坐标系的原点放牧,打算在群星断其生路前转移至安全地点。

此次共有M (1 ≤ M ≤ 50,000)颗流星来袭,流星i将在时间点Ti (0 ≤ Ti  ≤ 1,000) 袭击点 (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300)。每颗流星都将摧毁落点及其相邻四点的区域。

Bessie在0时刻时处于原点,且只能行于第一象限,以平行与坐标轴每秒一个单位长度的速度奔走于未被毁坏的相邻(通常为4)点上。在某点被摧毁的刹那及其往后的时刻,她都无法进入该点。

寻找Bessie到达安全地点所需的最短时间。

Input - 输入

* 第1行: 一个整数: M
* 第2..M+1行: 第i+1行包含由空格分隔的三个整数: Xi, Yi, and Ti

Output - 输出

* 仅一行: Bessie寻得安全点所花费的最短时间,无解则为-1。

Sample Input - 输入样例

4
0 0 2
2 1 2
1 1 2
0 3 5

Sample Output - 输出样例

5

代码:

#include<stdio.h>
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
int s[4]={0,0,1,-1};
int s1[4]={1,-1,0,0};
const int maxn=310;
int a[maxn][maxn];    //地图 
int vis[maxn][maxn];  //标记数组 
typedef long long ll;typedef struct node
{int x,y,time;bool operator< (const node&b)const {return time > b.time;}
}point;int min(int a,int b)
{return a>b?b:a;
}void bfs(int x,int y)
{memset(vis,0,sizeof(vis));priority_queue<point>q;point t;t.x=x;t.y=y;t.time=0;q.push(t);vis[x][y]=1;while(!q.empty()){point s2=q.top();q.pop();if(a[s2.x][s2.y]==-1){printf("%d\n",s2.time);return ;}for(int i=0;i<4;i++){point temp;temp.x=s2.x+s[i];temp.y=s2.y+s1[i];temp.time=s2.time+1;if(temp.x>=0&&temp.y>=0&&(a[temp.x][temp.y]==-1||a[temp.x][temp.y]>temp.time)){if(!vis[temp.x][temp.y])q.push(temp);vis[temp.x][temp.y]=1;}}}printf("-1\n");
}
int main()
{int n;while(scanf("%d",&n)!=EOF){int x,y,time;memset(a,-1,sizeof(a));for(int i=0;i<n;i++){scanf("%d%d%d",&x,&y,&time);//cin>>x>>y>>time;if(a[x][y]==-1)a[x][y]=time;elsea[x][y]=min(time,a[x][y]);for(int j=0;j<4;j++){int xx=x+s[j];int yy=y+s1[j];if(xx>=0&&yy>=0){if(a[xx][yy]==-1)a[xx][yy]=time;elsea[xx][yy]=min(a[xx][yy],time);}}}bfs(0,0);}return 0;
}

代码首先是把地图先处理一遍,因为有要求,流行爆炸过的地方不能走,和几秒后流行爆炸的地方是不能走的(在爆炸之前走过去)。对地图进行初始值操作地图全为 -1,流星炸过(将要炸)的地方标记为爆炸的时间,并且前后左右四个方向都会遭殃,也标记为爆炸时间,如果爆炸地点重复,就更新为最短的时间。这道题目的特殊性是先进行标记处理,然后再去BFS搜索最短的时间,因为有一些爆炸过的点作为障碍,就用优先队列(好像普通的队列也可以)对时间进行最小的排序,得到最小时间。

总结:对地图有一些更高的要求,就事先处理地图,处理好后,再进行BFS操作,又是一个新的思路,事先处理好地图的相关操作。

这篇关于POJ 3669(优先队列BFS)(对地图进行优化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929893

相关文章

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

Linux进程CPU绑定优化与实践过程

《Linux进程CPU绑定优化与实践过程》Linux支持进程绑定至特定CPU核心,通过sched_setaffinity系统调用和taskset工具实现,优化缓存效率与上下文切换,提升多核计算性能,适... 目录1. 多核处理器及并行计算概念1.1 多核处理器架构概述1.2 并行计算的含义及重要性1.3 并

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

linux解压缩 xxx.jar文件进行内部操作过程

《linux解压缩xxx.jar文件进行内部操作过程》:本文主要介绍linux解压缩xxx.jar文件进行内部操作,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、解压文件二、压缩文件总结一、解压文件1、把 xxx.jar 文件放在服务器上,并进入当前目录#

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

使用Python进行GRPC和Dubbo协议的高级测试

《使用Python进行GRPC和Dubbo协议的高级测试》GRPC(GoogleRemoteProcedureCall)是一种高性能、开源的远程过程调用(RPC)框架,Dubbo是一种高性能的分布式服... 目录01 GRPC测试安装gRPC编写.proto文件实现服务02 Dubbo测试1. 安装Dubb