Escape(有加速铭文)（优先队列）
题目：
BH is in a maze,the maze is a matrix,he wants to escape!
输入
The input consists of multiple test cases.
For each case,the first line contains 2 integers N,M( 1 <= N, M <= 100 ).
Each of the following N lines contain M characters. Each character means a cell of the map.
Here is the definition for chracter.
For a character in the map:
‘S’:BH’s start place,only one in the map.
‘E’:the goal cell,only one in the map.
‘.’:empty cell.
‘#’:obstacle cell.
‘A’:accelerated rune.
BH can move to 4 directions(up,down,left,right) in each step.It cost 2 seconds without accelerated rune.When he get accelerated rune,moving one step only cost 1 second.The buff lasts 5 seconds,and the time doesn’t stack when you get another accelerated rune.(that means in anytime BH gets an accelerated rune,the buff time become 5 seconds).
输出
The minimum time BH get to the goal cell,if he can’t,print “Please help BH!”.
输入：
5 5
…E
…
…
##…
S#…
5 8
…
…
…A…A
A######.
S…E
输出：
Please help BH!
12
题意 ：求S到E的最短耗费时间，可获得加速铭文，让每次移动只需1s，一个铭文时间为5秒，不可叠加；
分析，为什么要优先队列，按第二组来说，你先把右边入队列后，再把上边入队列后，结果最先到达的是右边开始的，结果为14；但是正确答案应该是12；故应该按加速剩与时间和走的时间来确定优先那个；
光优先队列还是会wa，必须用三维book数组标记，一维二维存坐标，那么第三个呢，存此时的加速剩余时间，为什么？列如有一种情况，加速符在一死角，你必须去吃了后再回来才是最优解得情况；
其他就是一个标准的宽搜问题了，基本模板；
c++代码如下：
这个题oj换行有点点问题
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include
#include
#include
#include
#pragma G++ optimize(2)
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double eps = 1e-12;
const int mod = 999911659;
typedef pair pii;
char e[110][110];
int n,m,sx,sy,mi;
bool book[110][110][8];
int way[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct Node{
int x,y,step,time;
friend bool operator < (const Node a,const Node b)
{
if(a.step==b.step) return a.timeb.step;
}
};
priority_queue qe;
void bfs()
{
while(!qe.empty()) qe.pop();
Node now,temp,ne;
book[sx][sy][0]=1;
now.x=sx,now.y=sy,now.step=0,now.time=0;
qe.push(now);
while(!qe.empty())
{
temp=qe.top();
qe.pop();
if(e[temp.x][temp.y]=='E')
{
mi=min(mi,temp.step);
break;
}else
{
for(int i=0;i<4;i++)
{
int dx=temp.x+way[i][0];
int dy=temp.y+way[i][1];
if(dxn||dym||e[dx][dy]=='#')
continue ;
if(temp.time>0)
{
ne.time=temp.time-1;
ne.step=temp.step+1;
}else
{
ne.step=temp.step+2;
ne.time=0;
}
if(e[dx][dy]=='A')
ne.time=5;
if(book[dx][dy][ne.time])
continue ;
book[dx][dy][ne.time]=1;
ne.x=dx;
ne.y=dy;
qe.push(ne);
}
}
}
return ;
}
int main(){
//IOS;
while(cin>>n>>m)
{
mi=INF;
memset(book,0,sizeof(book));
memset(e,0,sizeof(e));
for(int i=1;i<=n;i++)
for(int j=1;j>e[i][j];
if(e[i][j]=='S')
{
sx=i;
sy=j;
}
}
bfs();
if(mi==INF) cout<<"Please help BH!"<<"\r\n";
else cout<<mi<<"\r\n";
}
return 0;
}
如有问题，还请包涵，联系本人更改。
作者：ddgo
