Treasure of the Chimp Island hdu bfs

发布时间:2016-12-8 0:25:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Treasure of the Chimp Island hdu bfs",主要涉及到Treasure of the Chimp Island hdu bfs方面的内容,对于Treasure of the Chimp Island hdu bfs感兴趣的同学可以参考一下。

这道题又是一道水题,但是感觉好像大部分人都感觉难,可能我运气好,没做什么优化就800多ms飘过。。。。 我猜应该有很多人跟我一样懒,我就把题意说一下吧。一张地图里有一个宝藏,用‘$’来表示宝藏存放的地方,字母A,B,C。。。呢,就是进入地图的入口,只能从这些字母的地方进入地图,并且字母A代表不但是个门,这个门里面还有炸药,代表有1包炸药,B代表两包炸药,依次类推。’#‘也代表门,但是这个门里面没有炸药。你从一扇门里面进去,就不能从其他门里面捡炸药了。’*‘代表墙,不能过,'.'代表路,可以走,并且走这种路不需要耗费时间,数字1到9代表石头,你经过这些石头要耗费1到9的时间,你也可以不费时间,直接耗费一包炸药。问最短时间到达宝藏。 思路是遍历每个门,从每个门开始做一次bfs,取最短的时间就是答案。这个bfs就是最普通的bfs,我唯一做的优化就是设立一个标记数组tag[i][j][k],表示经过map[i][j]这个点的所有路径中,剩下K包炸药所要走的最小路径,比如tag[2][1][3]= 2表示经过点(2,1)并且还剩下3包炸药所需要的最小时间是2,如果有另外一条路径到达这里,并且剩下3包炸药,只需要耗费1的时间,那么就入队,1天以上的就不入队了。当然有一个优化是现在的时间已经超过了已知的答案,就不用再入队了。然后就是碰到石头,要选择炸掉入一次队,不炸掉入一次队。还有一点,这里的bfs如果搜到终点了不能马上返回,先到的不一定是时间最少的,只是说明与起点的距离最短。 告诉大家一个小技巧,其实像这种多种限制的题目,标记数组就多设置一维作为约束条件。比如杭电的nightma,Kaitou Kid - The Phantom Thief (2),都是有两种约束条件的,就是除了步数,还有爆炸剩余时间,得到宝石的与否。一般都能过。 #include<stdio.h> #include<iostream> #include<memory> #include<queue> #include<string.h> using namespace std; char map[105][105]; int dir[4][2] = {0,-1,0,1,-1,0,1,0},n,m,tag[105][105][27]; struct node { int step,rest,x,y; }; bool check(node temp) { return (temp.x < n && temp.y < m && temp.x >= 0 && temp.y >= 0 && map[temp.x][temp.y] != '*' && map[temp.x][temp.y] != '#'); } int bfs(int x,int y) { queue<node>q; int rest,ans = 0x7fffffff,t = 0; if(map[x][y] == '#') rest = 0; else rest = map[x][y] - 'A' + 1;//把字母转化成炸弹数。 node now = {0,rest,x,y}; tag[x][y][rest] = 0; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(map[now.x][now.y] == '$' && now.step < ans) { ans = now.step; continue;//到终点了就没必要搜了,但是先到的不一定是正确答案 } for(int i = 0;i < 4;++i) { node temp = now; temp.x += dir[i][0]; temp.y += dir[i][1]; if(check(temp) && (map[temp.x][temp.y] > 'Z' || map[temp.x][temp.y] < 'A') && (temp.step < tag[temp.x][temp.y][temp.rest]) && temp.step < ans) { tag[temp.x][temp.y][temp.rest] = temp.step; if(map[temp.x][temp.y] <= '9' && map[temp.x][temp.y] >= '0') { if(temp.rest) { temp.rest--;//炸掉,入队 q.push(temp); temp.rest++;//不炸掉,入队 } temp.step += map[temp.x][temp.y] - '0'; } q.push(temp);//这里就是不炸掉入队 } } } return ans; } int main() { while(1) { for(n = 0;;++n) { scanf("%c",&map[n][0]); if(map[n][0] == '\n') break; for(int j = 1;;++j) { scanf("%c",&map[n][j]); if(map[n][j] == '\n') { map[n][j] = 0; break; } } m = j; if(strcmp(map[n],"--") == 0) return 0; }//输入有点麻烦 for(int i = 0;i < n;++i) for(int j = 0;j < m;++j) for(int k = 0;k < 27;++k) tag[i][j][k] = 0x7fffffff; //标记数组,表示经过这个点,剩下k包炸药所需要的最短时间 int ans = 0x7fffffff; for(i = 0;i < n;++i) { for(int j = 0;j < m;++j) { if(map[i][j] == '#' || (map[i][j] >= 'A' && map[i][j] <= 'Z')) { int temp = bfs(i,j);//从每个点开始bfs if(temp < ans) ans = temp; } } } if(ans == 0x7fffffff) printf("IMPOSSIBLE\n"); else printf("%d\n",ans); } return 0; }

上一篇:算法小题二(求高次方程的一个实根2x^4-4x^3+6X^2-8x-8=0)
下一篇:《经典车》搭载保时捷发动机的面包车

相关文章

相关评论