Prison Break
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3165 Accepted Submission(s): 804
were put into jail, including our clever Micheal#1. Now it’s time to escape, but Micheal#1 needs an optimal plan and he contacts you, one of his human friends, for help.
The jail area is a rectangle contains n×m little grids, each grid might be one of the following:
1) Empty area, represented by a capital letter ‘S’.
2) The starting position of Micheal#1, represented by a capital letter ‘F’.
3) Energy pool, represented by a capital letter ‘G’. When entering an energy pool, Micheal#1 can use it to charge his battery ONLY ONCE. After the charging, Micheal#1’s battery will become FULL and the energy pool will become an empty area. Of course, passing
an energy pool without using it is allowed.
4) Laser sensor, represented by a capital letter ‘D’. Since it is extremely sensitive, Micheal#1 cannot step into a grid with a laser sensor.
5) Power switch, represented by a capital letter ‘Y’. Once Micheal#1 steps into a grid with a Power switch, he will certainly turn it off.
In order to escape from the jail, Micheal#1 need to turn off all the power switches to stop the electric web on the roof—then he can just fly away. Moving to an adjacent grid (directly up, down, left or right) will cost 1 unit of energy and only moving operation
costs energy. Of course, Micheal#1 cannot move when his battery contains no energy.
The larger the battery is, the more energy it can save. But larger battery means more weight and higher probability of being found by the weight sensor. So Micheal#1 needs to make his battery as small as possible, and still large enough to hold all energy he
need. Assuming that the size of the battery equals to maximum units of energy that can be saved in the battery, and Micheal#1 is fully charged at the beginning, Please tell him the minimum size of the battery needed for his Prison break.
of the jail.You can assume that 1<=n,m<=15, and the sum of energy pools and power switches is less than 15.
5 5 GDDSS SSSFS SYGYS SGSYS SSYSS 0 0
4
2010 Asia Hangzhou Regional Contest
题意:一个人背着一个有一定容量的电池,每走一步耗用1,D:不能走,S:空地 ,G:能量池,把背的容量电池充满(只能用一次)可取可不取,F:走点,Y:开关,这个人必须全部关闭开关才能走出地牢,问最小背多大的容量电池才能走出。
注意:在一个位置,虽然某一个状态走过了,但当前剩余能量比前一次走过的能量大,则也要放入队列中。
解题:先求出最大容量,不用管G,再用二分+bfs出最小须要的容量。
#include<iostream> #include<queue> using namespace std; typedef struct nnn { int x,y,G,Y,st; }node; char map[16][16]; int vist[16][16][1<<16]; int n,m,sta_y,k,sx,sy,dir[4][2]={0,1,0,-1,1,0,-1,0},tmap[16][16]; void init() { for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int s=0;s<(1<<k);s++) vist[i][j][s]=-1; } int bfs() { if(sta_y==0)return 0; queue<node>q; node p,pp; init(); p.x=sx; p.y=sy; p.Y=0; p.st=0; vist[sx][sy][0]=1; q.push(p); while(!q.empty()) { p=q.front(); q.pop(); for(int e=0;e<4;e++) { int tx,ty; tx=p.x+dir[e][0]; ty=p.y+dir[e][1]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]!='D') { pp.x=tx; pp.y=ty; pp.st=p.st+1; pp.Y=p.Y; if(map[tx][ty]=='Y')pp.Y|=(1<<tmap[tx][ty]); if(pp.Y==sta_y)return pp.st; if(vist[tx][ty][pp.Y]==-1) q.push(pp),vist[tx][ty][pp.Y]=1; } } } return -1; } int bfs1(int maxst) { queue<node>q; node p,pp; init(); p.x=sx; p.y=sy; p.G=0; p.Y=0; p.st=maxst; vist[sx][sy][0]=maxst;//注意 q.push(p); while(!q.empty()) { p=q.front(); q.pop(); for(int e=0;e<4;e++) { int tx,ty; tx=p.x+dir[e][0]; ty=p.y+dir[e][1]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]!='D') { pp.x=tx; pp.y=ty; pp.st=p.st-1; pp.Y=p.Y; pp.G=p.G; if(map[tx][ty]=='Y') { pp.Y|=(1<<tmap[tx][ty]); if(pp.Y==sta_y)return 1; } else if(map[tx][ty]=='G') { if((pp.G&(1<<tmap[tx][ty]))==0) { pp.G|=(1<<tmap[tx][ty]); pp.st=maxst; if(vist[tx][ty][pp.G|pp.Y]<maxst)//注意 q.push(pp); vist[tx][ty][pp.G|pp.Y]=maxst; } pp.G=p.G; pp.st=p.st-1; } if(pp.st&&vist[tx][ty][pp.G|pp.Y]<pp.st)//注意 q.push(pp),vist[tx][ty][pp.G|pp.Y]=pp.st; } } } return 0; } int main() { int minst; while(scanf("%d%d",&n,&m)>0&&m+n!=0) { for(int i=0;i<n;i++)scanf("%s",map[i]); k=0; sta_y=0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(map[i][j]=='G') { tmap[i][j]=k; k++; } else if(map[i][j]=='Y') { tmap[i][j]=k; sta_y|=(1<<k); k++; } else if(map[i][j]=='F') sx=i,sy=j; minst=bfs(); if(minst<=1) { printf("%d\n",minst);continue; } int l,mm; l=1; while(l<minst) { mm=(l+minst)/2; if(bfs1(mm)==1)minst=mm; else l=mm+1; } printf("%d\n",minst); } }