Escape（反思与总结）

题目描述：

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来记录同一个点出现的不同能量值，如果没标记过，就要标记起来并且压入的队列。

代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 bool vis[maxn][maxn][];

 int way[][] = { {,}, {,-}, {,}, {-,} };

 int mins;

 struct node{

     int x,y,step,buff;

     friend bool operator < (const node a, const node b)

     {

         if(a.step == b.step)    return a.buff < b.buff;

         return a.step > b.step;

     }

 };

 priority_queue<node> que;

 int n, m, sx, sy, ex, ey;

 char a[maxn][maxn];

 void bfs(){

     node temp, next, first;

     vis[sx][sy][] = true;

     first.x = sx, first.y = sy, first.step = , first.buff = ;

     que.push(first);

     while(!que.empty()){

         temp = que.top();

         que.pop();

         if(temp.x == ex && temp.y == ey){

             mins = min(mins, temp.step);

             break;

         }

         else

         {

             for(int i = ; i < ; i++)

             {

                 int dx = temp.x+way[i][];

                 int dy = temp.y+way[i][];

                 if(dx< || dx>=n || dy< || dy>=m || a[dx][dy] == '#')    continue;

                 if(temp.buff > ){

                     next.buff = temp.buff - ;

                     next.step = temp.step + ;

                 }else{

                     next.buff = ;

                     next.step = temp.step + ;

                 }

                 if(a[dx][dy] == 'A')

                     next.buff = ;

                 if(vis[dx][dy][next.buff])

                     continue;

                 vis[dx][dy][next.buff] = true;

                 next.x = dx, next.y = dy;

                 que.push(next);

             }

         }

     }

     return ;

 }

 int main()

 {

     while(cin >> n >> m){

         mins = INF;

         memset(vis, false, sizeof(vis));

         memset(a, , sizeof(a));

         while(!que.empty())    que.pop();

         for(int i = ; i < n; i++)

             for(int j = ; j < m; j++)

                 cin >> a[i][j];

         for(int i = ; i < n; i++)

             for(int j = ; j < m; j++){

                 if(a[i][j] == 'S')

                     sx = i, sy = j;

                 else if(a[i][j] == 'E')

                     ex = i, ey = j;

             }

         bfs();

         if(mins == INF)

             cout << "Please help BH!" << "\r\n";

         else

             cout << mins << "\r\n";

     }

     return ;

  }

巴特西

Escape（反思与总结）

题目描述：

Input：

Output：

理解：

代码如下：

最新文章

热门文章