hdu5025 (2014广州网赛1004)Saving Tang Monk

2024-01-28 06:38

本文主要是介绍hdu5025 (2014广州网赛1004)Saving Tang Monk,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        题意:类似走迷宫的一个题,给一个n*n的地图,从K开始走到T,标#号的地方不能走。走的过程中,要按顺序拿m种钥匙(在地图中是数字,每种可能有多把),如果遇到蛇S,需要花1的额外时间把它打死。输出走到终点的最短时间。

        思路:状态空间搜索。如果把钥匙的取得情况和蛇的生存情况也看成状态,就简单多了。状态第一、二维是行和列。钥匙最多9,需要按顺序拿,所以第三维开10就足够了。蛇的生存情况可以用5位二进制表示,也就是第四维开32。然后用优先队列搜。比赛的时候这题A出来真是扬眉吐气~


#include <iostream>               
#include <stdio.h>               
#include <cmath>               
#include <algorithm>               
#include <iomanip>               
#include <cstdlib>               
#include <string>               
#include <string.h>               
#include <vector>               
#include <queue>               
#include <stack>               
#include <map>             
#include <assert.h>    
#include <set>             
#include <ctype.h>                    
#define ll long long           
#define max3(a,b,c) max(a,max(b,c))           using namespace std;  char mp[110][110];
int a[110][110][10][32];int dn[]={-1,1,0,0};
int dm[]={0,0,-1,1};struct node{int nn;int mm;int key;int snk;int dis;node(int a,int b,int c,int d,int ee){nn=a; mm=b; key=c; snk=d; dis=ee;}bool operator<(node b)const{return dis>b.dis;}
};int main(){int n,m;while(cin>>n>>m){if(n==0&&m==0)break;memset(a,-1,sizeof(a));int snk=0;int startn;int startm;int endn;int endm;for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);for(int j=1;j<=n;j++){if(mp[i][j]=='K'){startn=i;startm=j;}else if(mp[i][j]=='S'){mp[i][j]=snk+'A';snk++;}else if(mp[i][j]=='T'){endn=i;endm=j;}}}node start(startn,startm,0,0,0); a[startn][startm][0][0]=0;priority_queue<node> que; que.push(start);int ans=0;while(!que.empty()){node cur=que.top(); que.pop();int cn=cur.nn;int cm=cur.mm;int ckey=cur.key;int csnk=cur.snk;int cdis=cur.dis;if(cn==endn&&cm==endm&&ckey==m){ans=cdis;break;}for(int d=0;d<4;d++){int newn=cn+dn[d];int newm=cm+dm[d];if( newn<1||newn>n||newm<1||newm>n )continue;if( mp[newn][newm]=='#' )continue;if( mp[newn][newm]=='.'||mp[newn][newm]=='T'||mp[newn][newm]=='K' ){if(a[newn][newm][ckey][csnk]==-1){a[newn][newm][ckey][csnk]=cdis+1;node nd(newn,newm,ckey,csnk,cdis+1);que.push(nd);}}if( mp[newn][newm]>='A'&&mp[newn][newm]<='E' ){int tmp=mp[newn][newm]-'A';tmp=(1<<tmp);if(tmp&csnk){if(a[newn][newm][ckey][csnk]==-1){a[newn][newm][ckey][csnk]=cdis+1;node nd(newn,newm,ckey,csnk,cdis+1);que.push(nd);}}else{if(a[newn][newm][ckey][csnk|tmp]==-1){a[newn][newm][ckey][csnk|tmp]=cdis+2;node nd(newn,newm,ckey,csnk|tmp,cdis+2);que.push(nd);}}}if( mp[newn][newm]>='1'&&mp[newn][newm]<='9' ){int tmp=mp[newn][newm]-'0';if(tmp==ckey+1){if(a[newn][newm][ckey+1][csnk]==-1){a[newn][newm][ckey+1][csnk]=cdis+1;node nd(newn,newm,ckey+1,csnk,cdis+1);que.push(nd);}}else{if(a[newn][newm][ckey][csnk]==-1){a[newn][newm][ckey][csnk]=cdis+1;node nd(newn,newm,ckey,csnk,cdis+1);que.push(nd);}}}}}if(ans==0){cout<<"impossible"<<endl;}else{cout<<ans<<endl;}}return 0;
}


这篇关于hdu5025 (2014广州网赛1004)Saving Tang Monk的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

2014年暑假培训 - 数论

A银河上的星星 /**************************************************************     Problem: 1014     User: DoubleQ     Language: C++     Result: Accepted     Time:190 ms     Memor

2014暑假集训搜索专题

A - 漫步校园 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Description LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划

[置顶] 2014训练计划进阶版

动态规划: 区间dp,树状dp,数位dphdu3555, sgu258, sgu390  队列优化: zoj3399 最小表示法的状态压缩DP: spoj2159  专题链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=38881#overview 专题链接: http://acm.hust.edu.cn/vjudg

[置顶] 2014训练计划

每个专题结束后会有5小时的专题赛~ 1、hustOJ目前支持谷歌、火狐浏览器等部分浏览器。 2、欢迎吐槽~ 3、推荐该阶段用书(以下具体算法实现多数可在此书中找到详解):算法竞赛入门经典之训练指南(刘汝佳) 4、题解报告:专题中的题目多是经典题目,百度搜索即有详细解答~ 5、专题相关知识点红字标出,建议先百度红字部分,有助于专题学习~ 6、专题时间会在"ACM 今天你AC了吗?"(12

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日,他们俩30岁生日那天,当年

2014年ACM/ICPC亚洲区现场赛广州赛区总结

本来不想提这件事的,后来学姐找我谈心时提到这件事,我突然意识到在这件事情上我错了一次,明明答应的去参加这场比赛,最后临时决定不去......其实中间有很多很多原因 1:我和tyh,sxk临时不去主要是广州太远,我们身上money不够,呵呵。。。别笑我们,你以为我们是高富帅啊,去一趟广州消费要2个月的生活费,奖学金又没发,你让我找我妈要她辛辛苦苦挣来的工资吗?!从哈尔滨到广州单来回的火车票每个人就