HDU 3442 Three Kingdoms 优先队列(非状压做法)

2024-01-02 12:30

本文主要是介绍HDU 3442 Three Kingdoms 优先队列(非状压做法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给出一个maze(某三国志类型游戏地图

$ 代表起点

!代表终点

.   代表路

#  代表墙

A,B,C,D,E分别代表不同的防御塔,其射程和攻击力各不相同。但其中只有C是可以走的。且每种防御塔只会造成一次伤害。

求最小伤害,到不了终点惯例输出-1

思路:先用bfs把地图染色,记住每个点都会收到什么伤害,这里用set实现。

再bfs寻路,每个点的所有状态用点集表示(set<set<int> >,set<int>是点集,就是一种状态,而set<set<int> >就是一点的状态集),在bfs时确定同一个点不会有重复的状态被压入队列。

又考虑到状态较多,可能会MLE,使用优先队列,略去多余的状态点。

非状压做法代码:

<span style="font-size:14px;">#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
using namespace std;
bool vis[60][60];
set <int> maze[60][60];
int dirx[]={0,-1,1,0};
int diry[]={-1,0,0,1};
set <int> em;
typedef struct Node{int x;int y;int sum;public:Node(int xx,int yy,int ss){x=xx;y=yy;sum=ss;}
}Node;
typedef struct node{int x;int y;set <int> s;int ans;bool operator < (const node &a)const{if(a.ans==ans){if(a.x==x)return a.y<y;return a.x<x;}return a.ans<ans;}public:node(int xx,int yy,set<int> ss,int a){x=xx;y=yy;s=ss;a=0;set<int>::iterator it;for(it=s.begin();it!=s.end();it++)a+=*it;ans=a;}
}node;
const int INF=0x3f3f3f3f;
int n,m,stx,sty,enx,eny;
void bfs(int x,int y,int r,int d){//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。bfs对图染色queue <Node> que;que.push(Node(x,y,r));bool tvis[60][60]={0};tvis[x][y]=1;while(!que.empty()){Node t=que.front();que.pop();if(t.sum<0)continue;else{maze[t.x][t.y].insert(d);//。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。一点上的初始状态(会被哪些塔攻击到)for(int i=0;i<4;i++){int xx=dirx[i]+t.x;int yy=diry[i]+t.y;if(tvis[xx][yy]||xx<0||xx>=n||yy<0||yy>=m)continue;que.push(Node(xx,yy,t.sum-1));tvis[xx][yy]=0;}}}return ;
}
int main()
{int T;scanf("%d",&T);getchar();em.clear();for(int ppp=1;ppp<=T;ppp++){scanf("%d %d",&n,&m);getchar();memset(vis,0,sizeof(vis));for(int i=0;i<60;i++)for(int j=0;j<60;j++)maze[i][j].clear();char x;int ans=INF;enx=INF;eny=INF;for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%c",&x);if(x=='A'){bfs(i,j,2,1);vis[i][j]=1;}else if(x=='B'){bfs(i,j,3,2);vis[i][j]=1;}else if(x=='C'){bfs(i,j,0,3);}else if(x=='D'){bfs(i,j,2,4);vis[i][j]=1;}else if(x=='E'){bfs(i,j,1,5);vis[i][j]=1;}else if(x=='$'){stx=i;sty=j;}else if(x=='!'){enx=i;eny=j;}else if(x=='#'){vis[i][j]=1;}}getchar();}priority_queue <node> que;que.push(node(stx,sty,em,0));set <set<int> > event[60][60];//。。。。。。。。。。。。。。。。。。。。。。。。。。。。地图上每点的状态集初始为空for(int i=0;i<n;i++){for(int j=0;j<m;j++){event[i][j].clear();}}event[stx][sty].insert(em);while(!que.empty()){node t=que.top();que.pop();if(t.x==enx&&t.y==eny){ans=t.ans;break;}else{for(int i=0;i<4;i++){int xx=dirx[i]+t.x;int yy=diry[i]+t.y;if(xx<0||yy<0||xx>=n||yy>=m||vis[xx][yy]) continue;set <int> mix;set_union(t.s.begin(),t.s.end(),maze[xx][yy].begin(),maze[xx][yy].end(),inserter(mix,mix.begin()));if(event[xx][yy].find(mix)==event[xx][yy].end()){//。。。。。。。。。。。。。。。若新的状态在点上没有出现过,就入队que.push(node(xx,yy,mix,0));event[xx][yy].insert(mix);//。。。。。。。。。。。。。。。。。。。。。。。。更新点的状态集}}}}if(ans==INF)ans=-1;printf("Case %d: %d\n",ppp,ans);}
}</span><span style="font-size:24px;">
</span>

Description

Three Kingdoms is a funny game. Often Liu Bei is weak and has to run away,so in the game Liu Bei has a skill called "Dunzou". This time you are playing the role of Liu Bei.As Cao Cao's power is so strong, there is nothing you can do but escaping. Please select an optimal path to achieve the purpose .
To simplify the problem, Liu Bei can only move in one of the four direction (up, down,right,left) each time. The map contains the following characters: 
‘A’ : Representative of watchtower, which has an attack range of 2(measured by Manhattan distance),and an attack damage of 1. 
‘B’ : Representative of Fort, which has an attack range of 3(measured by Manhattan distance),and an attack damage of 2. 
‘C’ : Representative of Flame, which has an attack damage of 3 to those who step onto it. 
‘D’ : Representative of Archer, which has anattack range of 2(measured by Manhattan distance), and an attack damage of 4. 
‘E’ : Representative of Ordinary soldier, which has anattack range of 1(measured by Manhattan distance), and an attack damage of 5. 
‘$’ : Representative of Liu Bei. 
‘!’ : Representative of Destination. 
'#' : Representative of obstacles 
‘.’ : Representative of floor. 
Liu Bei can not enter watchtower, forts, Archers, ordinary soldiers,But he can step onto flame or floor. 
Some important rules you should note: 
1.  Liu Bei will not be hurt by the same thing twice.For example,if Liu Bei has been hurt by one watchtower before,then he step into the attack range of some watchtower later,he will not be hurt. 
2.  When Liu Bei reach the destination,you should first judge the attack damage at the destination then finish the game. 
3.  You needn’t judge the attack damage at the start position. 
Please choose a path which LiuBei would cost the least HP. 

Input

In the first line there is an integer T, indicates the number of test cases.(T<=60) 
In each case,the first line of the input contains two integer n,m(1<=n,m<=50),reperesenting the size of map(n*m).Then follow n lines,each line contain m characters. 
There may be some blank lines between each case. 

Output

For each test case , output “Case d: “ where d is the case number counted from one.If Liu Bei can reach the destination then output the minimum HP LiuBei may lose, otherwise output -1.

Sample Input

1
4 3
.$.
ACB
ACB
.!.

Sample Output

Case 1: 6


这篇关于HDU 3442 Three Kingdoms 优先队列(非状压做法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :