網頁

2014年2月27日 星期四

UVa 11624 Fire

題意:
  J在一個迷宮裡,迷宮有"不只一個"起火點F,J一分鐘移動一步,而火焰一分鐘也會向上下左右蔓延一步,J只要碰到迷宮的邊緣即可逃走,確認J是否能逃走,如果可以,輸出要走的最短步數。

想法:
  將每個起火點用vector(或array)存下來,然後同時用兩個BFS,先讓所有起火點先動一步,再讓J動一步,確認J是否能碰到迷宮的邊緣。

  用int Maze[1001][1001]來描述該迷宮的情況,我用-2代表起火點,-1代表牆壁('#'),0代表可以走的路,用BFS時,每次為了確認火焰都只動一步,因此勢必要記錄火焰走的步數,每次火焰走下一步時Maze[nxt_i][nxt_j] = Maze[cur_i][cur_j] - 1,用負數記錄火焰步數,而正數用來記錄Joe的步數。