UVA11624 Fire!

Lrixin 2021-01-20 原文

题目链接：https://vjudge.net/problem/UVA-11624
Description
乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。
Input
第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J
Output
对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出’IMPOSSIBLE’如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行

Sample Input

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F

Sample Output

3
IMPOSSIBLE

解题思路：因为火出现位置传播方向固定，所以何时何地会被火覆盖是固定的，只要先进行预处理得到某处在几分钟后会被大火覆盖，在进行BFS时经过某点时间小于这个时间就ok了，同时如果该点不会被大火覆盖那它对应的临界时间就是INF。进行两次BFS即可。

Cpp Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=1010;
int n,m;
char g[MAXN][MAXN];
queue<pair<int,int> >q;
int a[MAXN][MAXN];
int mmove[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs1()
{
    memset(a,-1,sizeof(a));
    while(!q.empty())q.pop();
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='F')
            {
                a[i][j]=0;
                q.push(make_pair(i,j));
            }
    while(!q.empty())
    {
        pair<int,int> tmp=q.front();
        q.pop();
        int x=tmp.first;
        int y=tmp.second;
        for(int i=0;i<4;i++)
        {
            int tx=x+mmove[i][0];
            int ty=y+mmove[i][1];
            if(tx<0||ty<0||tx>=n||ty>=m)continue;
            if(a[tx][ty]!=-1)continue;
            if(g[tx][ty]=='#')continue;
            a[tx][ty]=a[x][y]+1;
            q.push(make_pair(tx,ty));
        }
    }
}
int b[MAXN][MAXN];
int bfs2()
{
    memset(b,-1,sizeof(b));
    while(!q.empty())q.pop();
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='J')
            {
                q.push(make_pair(i,j));
                b[i][j]=0;
            }
    while( !q.empty() )
    {
        pair<int,int> tmp=q.front();
        q.pop();
        int x=tmp.first;
        int y=tmp.second;
        if(x==0 || y==0 || x==n-1 || y==m-1)
            return b[x][y]+1;
        for(int i=0;i<4;i++)
        {
            int tx=x+mmove[i][0];
            int ty=y+mmove[i][1];
            if(tx<0||ty<0||tx>=n||ty>=m)continue;
            if(b[tx][ty]!=-1)continue;
            if(g[tx][ty]=='#')continue;
            if(a[tx][ty]!=-1 && b[x][y]+1>=a[tx][ty])continue;
            b[tx][ty]=b[x][y]+1;
            q.push(make_pair(tx,ty));
        }
    }
    return -1;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);
        bfs1();
        int ans=bfs2();
        if(ans==-1)printf("IMPOSSIBLE\n");
        else printf("%d\n",ans);
    }
    return 0;
}