[UVa] 11624 Fire!.cpp

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int Maze[1001][1001]; // -2:'F', 0:'.', -1:'#'
struct point_type{
    int x;
    int y;
};
vector<queue<point_type>> QF; // 存每個起火點
const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int BFS(point_type J)
{
    queue<point_type> QJ; QJ.push(J);  // 存Joe
    point_type cur, nxt;
    int minute;
    while(!QJ.empty()) {
        for (int i = 0; i < QF.size(); ++i) { // 多個火焰都要各動一步
            if (!QF[i].empty()){
                cur = QF[i].front();
                minute = Maze[cur.x][cur.y]; // 讓該火焰只動完目前這一分鐘後 
            }
            while (!QF[i].empty()){
                cur = QF[i].front();
                if (Maze[cur.x][cur.y] != minute) break; // 就跳出queue 換成 J 移動
                QF[i].pop();
                for (int x = 0; x < 4; ++x) {
                    nxt.x = cur.x + direction[x][0];
                    nxt.y = cur.y + direction[x][1];
                    if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C) continue;

                    if (Maze[nxt.x][nxt.y] == 0) {
                        Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] - 1;
                        QF[i].push(nxt);
                    }
                }
            }
        }
        cur = QJ.front();
        minute = Maze[cur.x][cur.y];
        while (!QJ.empty()) {
            cur = QJ.front();
            if (Maze[cur.x][cur.y] != minute) break; //只動完一步後 就換火焰移動

            QJ.pop();
            for (int x = 0; x < 4; ++x) {
                nxt.x = cur.x + direction[x][0];
                nxt.y = cur.y + direction[x][1];
                if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C)
                    return Maze[cur.x][cur.y];
                if (Maze[nxt.x][nxt.y] == 0) {
                    Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] + 1;
                    QJ.push(nxt);
                }
            }
        }
    }
    return -1;
}
int main()
{
 //   freopen("input.txt","rt",stdin);
    int Case;
    char line[1005];
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d %d", &R, &C);
        point_type J;
        QF.clear();
        for (int i = 0; i < R; ++i) {
            scanf("%s", line);
            for (int j = 0; j < C; ++j) {
                if (line[j] == '.')
                    Maze[i][j] = 0;
                else if (line[j] == '#')
                    Maze[i][j] = -1;
                else if (line[j] == 'J') {
                    J = {i,j};
                    Maze[i][j] = 1;
                }
                else if (line[j] == 'F') {
                    queue<point_type> tmp;
                    tmp.push({i,j});
                    QF.push_back(tmp);
                    Maze[i][j] = -2;
                }
            }
        }
        int minute = BFS(J);
        if (minute == -1) puts("IMPOSSIBLE");
        else printf("%d\n", minute);
    }
    return 0;
}