Fire! UVA – 11624 （两步bfs）

题意

人要从迷宫走出去，火会向四个方向同时扩散

分析

两步bfs，先出火到达各地时的时间（设初始时间为0，人每走一步为1s，在着一步内火可以向四周可触及的方向同时扩散），然后在bfs人，人能在某地当且仅当所到时间小于火到达时间

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1000+10;
const int INF = 0x3f3f3f3f;
int R, C, tcases;
int begx, begy;
char maze[maxn][maxn];
int fire_time[maxn][maxn];
int per_time[maxn][maxn];
int vis[maxn][maxn];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> P;
queue<P> pos;
bool op(int a, int b)
{
    if(a >= 0 && a < R && b >= 0 && b < C)
        return true;
    return false;
}
void init()
{
    while(!pos.empty())
        pos.pop();
    memset(vis, 0, sizeof(vis));
    bool is_fire = false;       //看是否有火
    for(int i = 0; i < R; i++)
    {
        for(int j = 0; j < C; j++)
        {
            per_time[i][j] = INF;
            fire_time[i][j] = INF;
            if(maze[i][j] == 'J')
            {
                begx = i;
                begy = j;
                per_time[i][j] = 0;
            }
            if(maze[i][j] == 'F')
            {
                fire_time[i][j] = 0;
                vis[i][j] = 1;
                is_fire = true;
                pos.push(P(i, j));      //将初始时F的位置插入到队列中
            }
        }
    }
    if(!is_fire)
        return ;    while(!pos.empty())
    {
        P p = pos.front();
        pos.pop();  //该点周围已遍历，故删掉
        for(int i = 0; i < 4; i++)
        {
            int curx = p.first + dx[i], cury = p.second + dy[i];
            if(op(curx, cury) && !vis[curx][cury] && maze[curx][cury] != '#')
            {
                vis[curx][cury] = 1;
                fire_time[curx][cury] = fire_time[p.first][p.second] + 1;
                pos.push(P(curx, cury));
            }
        }
    }
}
int bfs()
{
    while(!pos.empty())
        pos.pop();
    memset(vis, 0, sizeof(vis));
    pos.push(P(begx, begy));    //把J的初始位置插入
    vis[begx][begy] = 1;
    while(!pos.empty())
    {
        P p = pos.front();
        pos.pop();
        for(int i = 0; i < 4; i++)
        {
            int curx = p.first + dx[i], cury = p.second + dy[i];
            if(!op(curx, cury))
                return per_time[p.first][p.second] + 1;
            if(!vis[curx][cury] && maze[curx][cury] == '.' && per_time[p.first][p.second] + 1 < fire_time[curx][cury])   //人先fire一步到达
            {
                vis[curx][cury] = 1;
                pos.push(P(curx, cury));
                per_time[curx][cury] = per_time[p.first][p.second] + 1;
            }
        }
    }
    return INF;}
int main()
{
    cin >> tcases;
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(tcases--)
    {
        cin >> R >> C;
        for(int i = 0; i < R; i++)
            scanf("%s", maze[i]);
        init(); //探寻F到达各个点时的时间，用bfs
        int ans = bfs();
        if(ans != INF)
            cout << ans << endl;
        else
            cout << "IMPOSSIBLE" << endl;
    }
}