Fire UVA

直接放題目連結吧ＵＶＡ１１６２４

一開始比較犯暈，不知道怎麼下手，因為火和人都在動，後來看了眼分析瞬間有了思路，人是受火的牽制的，先讓火自由蔓延，即先對火跑一遍BFS，得到火到達每一塊地方的時間，然後人再跑一遍BFS，根據火到達每一塊地方的時間來判斷能不能走，隻要越過邊界就直接退出，即得到了最小時間。需要注意的是，着火點F不止有一個，一開始我對每一個F點都跑一遍BFS，意料之中逾時，然後改進了一下，直接把F點加入隊列就行了，不用挨個跑

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int N = 1e3 + 5;
const int INF = 1e9;  //時間最大值

struct node
{
    int x, y, time;
};
int r, c;
char map[N][N];
bool vis[N][N];
int ftime[N][N];    //到達每一塊地方的時間，初始化為INF
int xx[4] = {1, 0, 0, -1};
int yy[4] = {0, 1, -1, 0};

queue<node> qf;   //存放火的全局隊列
void Fire_BFS()
{    
    struct node t, u;
    while(!qf.empty())
    {
        u = qf.front();
        qf.pop();
        for(int i = 0; i < 4; i++)
        {
            t.x = u.x + xx[i];
            t.y = u.y + yy[i];
            if(t.x >= 0 && t.x < r && t.y >= 0 && t.y < c && map[t.x][t.y] != '#')
            {
                if(!vis[t.x][t.y])
                {
                    t.time = u.time + 1;
                    qf.push(t);
                    vis[t.x][t.y] = 1;
                    if(t.time < ftime[t.x][t.y])  //目前時間比之前的小，更新時間
                        ftime[t.x][t.y] = t.time;
                }
            }
        }
    }
}
int Joe_BFS(int jx, int jy)
{
    queue<node> q;
    struct node t, u;
    memset(vis, 0, sizeof(vis));
    t.x = jx;
    t.y = jy;
    t.time = 0;
    q.push(t);
    vis[jx][jy] = 1;
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            t.x = u.x + xx[i];
            t.y = u.y + yy[i];
            t.time = u.time + 1;
            if(t.x >= 0 && t.x < r && t.y >= 0 && t.y < c)
            {
                if(map[t.x][t.y] != '#' && t.time < ftime[t.x][t.y] && !vis[t.x][t.y]) 
                {                           //人到達一個地方的時間一定要比火到達的時間要小
                    q.push(t);
                    vis[t.x][t.y] = 1;
                }
            }
            else
                return t.time;
        }
    }
    return 0;
}
int main()
{
    int t;
    int jx, jy;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &r, &c);
        for(int i = 0; i < r; i++)
            scanf("%s", map[i]);
        for(int i = 0; i < r; i++)
            for(int j = 0; j < c; j++)
                ftime[i][j] = INF;  //初始化時間
        while(!qf.empty())    //清空隊列
            qf.pop();
        struct node temp;
        for(int i = 0; i < r; i++)
            for(int j = 0; j < c; j++)
            {
                if(map[i][j] == 'F')
                {
                    temp.x = i;
                    temp.y = j;
                    temp.time = 0;
                    qf.push(temp);  //每一個着火點入隊
                    vis[i][j] = 1;
                }
                else if(map[i][j] == 'J')
                {
                    jx = i;
                    jy = j;
                }
            }
        memset(vis, 0, sizeof(vis));
        Fire_BFS();
        int cnt = Joe_BFS(jx, jy);
        if(cnt)
            printf("%d\n", cnt);
        else
            printf("IMPOSSIBLE\n");
    }
    return 0;
}