題目敘述
中秋節的時候有人在森林中烤肉,一不小心就釀成了火災,火勢非常猛烈,如果某個區域原本沒有著火,但是相鄰的區域著火了,那麼下一分鐘這個區域也會被火勢波及。你很不幸的身處於著火的森林中,不過好加在你隨身帶了筆記型電腦,而且你恰好有這個森林地圖的資料。由廣播得知,火勢於第 $1$ 分鐘發生於起火點 $F$,而現在已經是第 $T$ 分鐘了。你的位置在 $S$ 處,標記 $E$ 的位置代表安全的避難所,並且有直升機場可以搭乘直升機避難。地圖上標著 `*` 的地方代表不可通行的區域,`.` 則是代表可以通過的區域。時間緊迫!你得趕緊找安全的逃生路線!
座標化的森林的地圖是一個長 $17$ 單位、寬 $10$ 單位的一片土地,詳細狀況如下:
```
*****************
*...*.......**..*
**..*....*.*.*..*
*......*.**.**.**
*..**...**..**.**
**.....**..*.*..*
*....*..........*
*.....****.*...**
****.*.*........*
*****************
```
左上角的位置為 $(0,0)$,右下角的位置為 $(9,16)$。你每分鐘可以從一個區域移動至相鄰的區域(在這裡所有的相鄰都不包含對角線方向)。現在給定 $F,T$ 之值以及 $S,E$ 的位置,請你求出從 $S$ 到 $E$ 的最短時間。
輸入說明
第一行有兩個正整數 $FX$, $FY$,代表起火點F的座標。
第二 行有一個正整數 $T (1\le T\le 1000)$,代表已經歷時間。
第三行有四個正整數 $SX$, $SY$, $EX$, $EY$,代表你所在的位置以及安全避難所的位置。
你可以假設 $F,S,E$ 皆位於可通行處。且避難所不會著火,$F,S,E$ 互不重疊。
輸出說明
若可以安全逃離,請輸出從 $S$ 到 $E$ 的最短時間。若你發現身陷火場,或者你根本無法到達避難所的時候,請輸出 Help!
。
Sample Input
1 1
3
4 1 3 3
Sample Output
9
出處
95建中資訊培訓模擬試題一(Prob 5)
OJ連結
題解
Step: 0
可以利用 BFS 來模擬森林中的火勢蔓延的狀況。用 onFire
陣列記錄下每個格點第一次著火的時間。然後根據這個表格在 onEscape
陣列記錄下從 $S$ 出發不踩過火到該點的所有時間。在這裡分享一些有趣的實作小細節:
- 使用方向陣列:
dx[]
和dy[]
分別儲存四個方向所需要的位移數值。 - 在把座標放進
queue
的時候,依序放入 $x$ 和 $y$ 座標。取出時也按照這個順序取,就不需要寫麻煩的pair<int, int>
了。
/* by tmt514 */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<string> forest = {
"*****************",
"*...*.......**..*",
"**..*....*.*.*..*",
"*......*.**.**.**",
"*..**...**..**.**",
"**.....**..*.*..*",
"*....*..........*",
"*.....****.*...**",
"****.*.*........*",
"*****************",
};
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int onFire[10][17];
int onEscape[10][17];
void bfs(int mark[10][17], int hasFire[10][17], int sx, int sy, int T) {
queue<int> q;
// 如果一開始就著火了,就應該直接死掉。
if (hasFire && hasFire[sx][sy] <= T) return;
mark[sx][sy] = T;
q.push(sx);
q.push(sy);
while (!q.empty()) {
int x = q.front(); q.pop();
int y = q.front(); q.pop();
int t = mark[x][y];
// 依序考慮四個方向是否可通行,如果可通行的話加到佇列裡面。
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (forest[nx][ny] == '.' &&
mark[nx][ny] == 0 &&
(!hasFire || hasFire[nx][ny] == 0 || hasFire[nx][ny] > t+1)) {
mark[nx][ny] = t+1;
q.push(nx);
q.push(ny);
}
}
}
}
int main() {
int fx, fy, sx, sy, ex, ey, T;
cin >> fx >> fy >> T;
cin >> sx >> sy >> ex >> ey;
// 由於火勢不會燒到避難處,所以一開始要取巧把這格改掉。
forest[ex][ey] = 'E';
bfs(onFire, NULL, fx, fy, 1);
// 然後把它改回變成可以通行。
forest[ex][ey] = '.';
bfs(onEscape, onFire, sx, sy, T);
if (onEscape[ex][ey] > 0) {
cout << onEscape[ex][ey]-T << endl;
} else {
cout << "Help!" << endl;
}
return 0;
}
關於這題
很久很久以前的北市賽(在還沒有使用 CMS 系統和使用隨身碟/磁碟輸入以前),評分的時候都是手動輸入測試資料的。當時出的模擬練習,就有點想要效法這樣的出題風格,所以森林的地圖就變成這樣 hard-code 的風格了。
註:以前是紙本題目,所以連地圖也要在比賽進行時手刻上去 QAQ