題目描述：
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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85174.html
標籤：其他
上一篇：二叉搜索樹與雙向鏈表
下一篇：字串的排列