題目：

喬在迷宮中工作。不幸的是，迷宮的一部分著火了，迷宮的主人沒有制定火災的逃跑計劃。請幫助喬逃離迷宮。
根據喬在迷宮中的位置以及迷宮的哪個方塊著火，你必須確定火焰燒到他之前，喬是否可以離開迷宮，如果能離開他能跑多快。 喬和火每分鐘移動一個方格，上、下、左、右，四個方向中的一個?；饎菹蛩膫€方向同時蔓延。
喬可以從迷宮的任何一個邊界逃離迷宮。無論是喬還是火都不會到達有墻的位置。

輸入：

第一行輸入包含一個整數，即測試次數 每個測試用例的第一行包含兩個 整數R和C，用空格分隔，1≤R，C≤1000 下面R行中，每一行都包含C個字符，以及每個字符是以下之一： # 代表墻 . 代表空地，火和喬是可通行的 J 喬在迷宮中最初的位置，火和喬是可通行的 F 代表火 在每組測試中只有一個J

輸出：

對于每個測試用例，如果在火蔓延的時候燒到了喬，則喬無法逃出迷宮，輸出'IMPOSSIBLE'如果喬能逃出迷宮，則輸出喬最快可以在幾分鐘內安全逃出迷宮，每組輸出占一行

樣例：

分析：因為火出現位置傳播方向固定，所以何時何地會被火覆蓋是固定的，只要先進行預處理得到某處在幾分鐘后會被大火覆蓋，在進行BFS時經過某點時間小于這個時間就ok了，同時如果該點不會被大火覆蓋那它對應的臨界時間就是INF

1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<string> 6 #include<cstring> 7 #include<algorithm> 8 #include<functional> 9 #include<iomanip> 10 #include<numeric> 11 #include<cmath> 12 #include<queue> 13 #include<vector> 14 #include<set> 15 #include<cctype> 16 #define PI acos(-1.0) 17 const int INF = 0x3f3f3f3f; 18 const int NINF = -INF - 1; 19 typedef long long ll; 20 using namespace std; 21 int n, m, flag; 22 char maze[1005][1005];//迷宮 23 typedef pair<int, int> P; 24 int usedf[1005][1005], usedj[1005][1005];//火; 人 是否經過 25 int d[1005][1005], tim[1005][1005];//人；火 時間 26 int st, ed;//起點 27 int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; 28 queue<P> fire; 29 void ini()//預處理大火覆蓋所需時間（BFS） 30 { 31 while (fire.size()) 32 { 33 P rec = fire.front(); 34 fire.pop(); 35 for (int i = 0; i < 4; ++i) 36 { 37 int nx = rec.first + dx[i], ny = rec.second + dy[i]; 38 if (nx >= 0 && nx < n && ny >= 0 && ny < m && !usedf[nx][ny] && maze[nx][ny] != '#') 39 { 40 usedf[nx][ny] = 1; 41 fire.push(P(nx, ny)); 42 tim[nx][ny] = tim[rec.first][rec.second] + 1; 43 } 44 } 45 } 46 } 47 int bfs() 48 { 49 queue<P> q; 50 memset(usedj, 0, sizeof(usedj)); 51 for (int i = 0; i < n; ++i) 52 { 53 for (int j = 0; j < m; ++j) 54 d[i][j] = INF; 55 } 56 q.push(P(st, ed)); 57 usedj[st][ed] = 1; 58 d[st][ed] = 0; 59 P temp; 60 while(q.size()) 61 { 62 temp = q.front(); 63 q.pop(); 64 if (temp.first == 0 || temp.first == n - 1 || temp.second == 0 || temp.second == m - 1)//到達邊界即逃出 65 { 66 flag = 1; 67 break; 68 } 69 for (int i = 0; i < 4; ++i) 70 { 71 int nx = temp.first + dx[i], ny = temp.second + dy[i]; 72 if (nx >= 0 && nx < n && ny >= 0 && ny < m && !usedj[nx][ny] && maze[nx][ny] == '.' && d[temp.first][temp.second] + 1 < tim[nx][ny]) 73 { 74 usedj[nx][ny] = 1; 75 q.push(P(nx, ny)); 76 d[nx][ny] = d[temp.first][temp.second] + 1; 77 } 78 } 79 } 80 if (flag) return d[temp.first][temp.second] + 1; 81 else return -1; 82 } 83 int main() 84 { 85 int T; 86 cin >> T; 87 while (T--) 88 { 89 flag = 0; 90 cin >> n >> m; 91 memset(usedf, 0, sizeof(usedf));//預處理的BFS函數的初始化，寫在這里方便輸入時給特殊位置賦值 92 for (int i = 0; i < n; ++i) 93 { 94 for (int j = 0; j < m; ++j) 95 tim[i][j] = INF; 96 } 97 for (int i = 0; i < n; ++i) 98 { 99 for (int j = 0; j < m; ++j) 100 { 101 cin >> maze[i][j]; 102 if (maze[i][j] == 'J') st = i, ed = j; 103 if (maze[i][j] == 'F') 104 { 105 usedf[i][j] = 1; 106 tim[i][j] = 0; 107 fire.push(P(i, j)); 108 } 109 } 110 } 111 ini(); 112 int ans = bfs(); 113 if (ans != -1) cout << ans << endl; 114 else cout << "IMPOSSIBLE" << endl; 115 while(fire.size()) fire.pop(); 116 } 117 return 0; 118 }

?

轉載于:https://www.cnblogs.com/veasky/p/10975520.html

總結

以上是生活随笔為你收集整理的UVA11624 Fire!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。