UVaOJ-11624-Fire! 解題報告

UVaOJ-11624-Fire! 解題報告

一道十分優美的搜索題，暴露了我對BFS了解的還不夠。題意：Joe要逃離一個迷宮，迷宮中有地方起火了，在火開始燃燒的時候Joe也開始逃，火的蔓延方式與Joe的行動方式一樣，都是1個單位時間可以往上下左右四個方向各走一格。另外，迷宮內有牆，Joe與火都無法穿牆。現在給你一個圖，請問Joe能否從迷宮的邊界處逃出而不被火燒到，如果能的話請輸出最短的逃脫時間，不能的話輸出“IMPOSSIBLE”。其中，‘F’代表火，‘J’代表Joe，‘#’代表牆。

我的解題思路：這題首先注意的就是，起火點可能不止一個，也可能沒有起火點。其次是如果一個起火點被四周的牆給封閉起來了，那麼這個火就相當於沒有用了。為了判斷Joe走到某個點時這個點是否已經起火，我們需要知道每個點起火的時間。通過對每個初始起火點進行BFS就可以知道每個點的起火時間了，最開始我是每個起火點都BFS一次，然後TLE了，後來才發現，其實可以把每個初始起火點當成一個起火點的鄰節點加入隊列，這樣就只進行了一次BFS，從而獲得了每個點起火的時間（如果有些點不會起火，那麼這些點的時間就是初始化的INF）。最後從Joe的起點開始BFS一次，如果走到下一個點時那個點已經或者剛好著火了那就不能走，牆也不能走，只要走到邊界就說明可以走出迷宮了。

我的解題代碼：BFS

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define N 1001
#define INF 999999999

struct point        //定義點結構體
{
    int x, y;   //坐標
    int step;   //步數，相當於時間
};

int dx[] = {1, -1, 0, 0};   //方向向量
int dy[] = {0, 0, -1, 1};   //方向向量

int n, m, t;
char map[N][N];
int vis[N][N];          //記錄火或者人到達點花費的最少時間
point start, fire;      //起點和起火處
queue  q;

void Read();            //輸入

void Init();            //初始化

void FireBfs();         //先進行起火處的Bfs

void DataProcess();     //進行人的Bfs判斷能否逃離以及最少逃離時間

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        Read();
        Init();
        DataProcess();
    }
    return 0;
}

void Read()
{
    scanf("%d %d", &n, &m);
    for (int i=0; i= n || ny < 0 || ny >= m) continue;       //越界
            if (map[nx][ny] == '#' || vis[nx][ny] <= a.step + 1) continue;  //牆或者已經走過的點
            b.x = nx;
            b.y = ny;
            b.step = vis[nx][ny] = a.step + 1;
            q.push(b);
        }
    }
    return;
}

void DataProcess()
{
    point a, b;
    FireBfs();
    q.push(start);      //將人的起點加入隊列准備Bfs
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        for (int i=0; i<4; ++i)
        {
            int nx = a.x + dx[i];
            int ny = a.y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)     //成功走到邊界
            {
                printf("%d\n", a.step + 1);
                return;
            }
            if (map[nx][ny] == '#' || vis[nx][ny] <= a.step + 1) continue;  //遇到牆或者該點起火或者走過
            b.x = nx;
            b.y = ny;
            b.step = vis[nx][ny] = a.step + 1;
            q.push(b);
        }
    }
    puts("IMPOSSIBLE");
    return;
}