UVa 11624 基础BFS

白书训练指南上的第一道基础题，因为它在搜索中引入了超级源点，所以我自己试着做了一下，真的宛如发现新大陆一般，图论的建图技巧真的是在整个图论领域都十分适用啊。

因为UVa的尿性，写完去搜一下题解，居然有很多题解都是两次 bfs ……真是笑了

题意：
一个起火的迷宫，有很多起火的地点，给你初始位置，和起火地点，你的逃跑速度和火焰蔓延速度相等，问你能否跑出迷宫，若能，输出最短时间。

思路：
网上那些两遍bfs的应该是先一遍bfs处理出火焰蔓延到每一个格子的最短时间，在自己bfs时间加个时间大小判断的限制。
然而实际上，我们溶入超级源点的思路，然所有点一起开始跑，在同一个时间内，让所有火焰先跑，并加以标记，而人则把火焰和墙壁一起处理，避而不走。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;
const int maxn = 1010;

int row, col, st, en;
char mat[maxn][maxn];
bool vis[maxn][maxn];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

struct node {
    int x, y;
    int time;
    bool is_fire;
    node() {}
    node(int _x, int _y, int _time, bool _fire)
        : x(_x)
        , y(_y)
        , time(_time)
        , is_fire(_fire)
    {
    }
} tmp;

queue<node> que;

int bfs()
{
    memset(vis, 0, sizeof vis);
    vis[st][en] = true;
    int x, y, time;
    bool is_fire;
    while (!que.empty()) {
        tmp = que.front();
        que.pop();
        x = tmp.x, y = tmp.y, time = tmp.time, is_fire = tmp.is_fire;
        if (!is_fire && (x == 0 || x == row - 1 || y == 0 || y == col - 1))
            return time + 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < row && yy >= 0 && yy < col && !vis[xx][yy] && mat[xx][yy] != '#') {
                if (is_fire) {
                    mat[xx][yy] = 'F';
                    que.push(node(xx, yy, time + 1, true));
                } else if (mat[xx][yy] == 'F')
                    continue;
                else
                    que.push(node(xx, yy, time + 1, false));
                vis[xx][yy] = true;
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &row, &col);
        while (!que.empty())
            que.pop();
        for (int i = 0; i < row; i++)
            scanf("%s", mat[i]);
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 'F')
                    que.push(node(i, j, 0, true));
                else if (mat[i][j] == 'J')
                    st = i, en = j;
            }
        que.push(node(st, en, 0, false));
        int ans = bfs();
        if (ans == -1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ans);
    }
    return 0;
}