题目描述：

BH is in a maze,the maze is a matrix,he wants to escape!

Input：

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).

Output：

The minimum time BH get to the goal cell,if he can't,print "Please help BH!".

理解：

总体来说，这个游戏是要玩最短路hhh，但是要判断有无加速向，最开始只想着用二维数组来记录从起点到每一个点的最短路径（距离），然后用queue正常做，只不过在结构体中多用一个buff元素来判断是否有吃到加速，然后每一次 if(que.front().buff > 0) temp.buff = que.front().buff-1;但由于经过同一点时，可能会有不同的路径，并且也可能有更短的出现，在标记buff和最短路难以权衡。

于是在某大大怪大牛的提醒下，在结构体中用step来记录最短路（这样就可以更新相同点的最短路），然后就是本题最核心也最有意思的地方了，用优先队列处理数据~。。由于同一点都可能有不同的路径，而不同的路径就会有可能有的路径有buff，有的没有（也可以理解为，同一个点先去捡一个buff，大致捡了buff的路径通常会最短？这个有待我思考。）于是用一个三维vis来记录同一个点出现的不同能量值，如果没标记过，就要标记起来并且压入的队列。

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 105;
 4 const int INF = 0x3f3f3f3f;
 5 bool vis[maxn][maxn][10];
 6 int way[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} };
 7 int mins;
 8 struct node{
 9     int x,y,step,buff;
10     friend bool operator < (const node a, const node b)
11     {
12         if(a.step == b.step)    return a.buff < b.buff;
13         return a.step > b.step;
14     }
15 };
16 priority_queue<node> que;
17 int n, m, sx, sy, ex, ey;
18 char a[maxn][maxn];
19 void bfs(){
20     node temp, next, first;
21     vis[sx][sy][0] = true;
22     first.x = sx, first.y = sy, first.step = 0, first.buff = 0;
23     que.push(first);
24     while(!que.empty()){
25         temp = que.top();
26         que.pop();
27         if(temp.x == ex && temp.y == ey){
28             mins = min(mins, temp.step);
29             break;
30         }
31         else
32         {
33             for(int i = 0; i < 4; i++)
34             {
35                 int dx = temp.x+way[i][0];
36                 int dy = temp.y+way[i][1];
37                 if(dx<0 || dx>=n || dy<0 || dy>=m || a[dx][dy] == '#')    continue;
38                 if(temp.buff > 0){
39                     next.buff = temp.buff - 1;
40                     next.step = temp.step + 1;
41                 }else{
42                     next.buff = 0;
43                     next.step = temp.step + 2;
44                 }
45                 if(a[dx][dy] == 'A')
46                     next.buff = 5;
47                 if(vis[dx][dy][next.buff])
48                     continue;
49                 vis[dx][dy][next.buff] = true;
50                 next.x = dx, next.y = dy;
51                 que.push(next);
52             }
53         }
54     }
55     return ;
56 }
57 
58 int main()
59 {
60     while(cin >> n >> m){
61         mins = INF;
62         memset(vis, false, sizeof(vis));
63         memset(a, 0, sizeof(a));
64         while(!que.empty())    que.pop();
65         for(int i = 0; i < n; i++)
66             for(int j = 0; j < m; j++)
67                 cin >> a[i][j];
68         for(int i = 0; i < n; i++)
69             for(int j = 0; j < m; j++){
70                 if(a[i][j] == 'S')
71                     sx = i, sy = j;
72                 else if(a[i][j] == 'E')
73                     ex = i, ey = j;
74             }
75         bfs();
76         if(mins == INF)
77             cout << "Please help BH!" << "\r\n";
78         else
79             cout << mins << "\r\n";
80     }
81     return 0;
82  }