題目敘述

中秋節的時候有人在森林中烤肉,一不小心就釀成了火災,火勢非常猛烈,如果某個區域原本沒有著火,但是相鄰的區域著火了,那麼下一分鐘這個區域也會被火勢波及。你很不幸的身處於著火的森林中,不過好加在你隨身帶了筆記型電腦,而且你恰好有這個森林地圖的資料。由廣播得知,火勢於第 $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
******************F..*.......**..***..*....*.*.*..**..E...*.**.**.***..**...**..**.****.....**..*.*..**....*..........**.....****.*...******.*.*........******************

可以利用 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

其他推薦題解

本文由卡恩(tmt514)撰寫。 本站使用 GasbyJS 搭配 Bulma 製作,其原始碼為 MIT 授權。 網站內容除了題源以外,若無特別說明皆為創用 CC-BY-NC-SA 4.0 授權。 題源部份若有版權爭議還請與我聯繫,感恩。