【UVA - 11624】Fire!

佚名 5年前 (2019-07-03) 算法 1167人围观抢沙发百度已收录

-->Fire!

直接上中文

Descriptions:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮
助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，
乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。
乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。

输入

第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J

输出

对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出'IMPOSSIBLE'
如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行

样例输入

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

样例输出

3
IMPOSSIBLE

题目链接：

https://vjudge.net/problem/UVA-11624

注意火不止一个，火是固定的且火走过的地方时间也是一样的，所以可以先把火走的地方需要的时间处理一下，然后再对人bfs，多加一个条件，人在这个地方的时间要小于火在这个地方的时间

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int T,n,m;
char mp[1005][1005];//原始地图
int visfire[1005][1005];//记录火是否烧过
int vispeople[1005][1005];//记录人是否走过
int firetime[1005][1005];//火经过这个地方的时间
int peopletime[1005][1005];//人经过这个地方的时间
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//四个方向
struct node
{
    int x,y;//坐标
};
node now,net;
queue<node>fire;//两个队列 火和人
queue<node>people;
void judgetime()//预处理火经过的地方的时间
{
    while(!fire.empty())
    {
        now=fire.front();
        fire.pop();
        for(int i=0; i<4; i++)//四种走法
        {
            int tx=now.x+dt[i][0];
            int ty=now.y+dt[i][1];
            if(tx>=0&&tx<n&&ty>=0&&ty<m&&!visfire[tx][ty]&&mp[tx][ty]!='#')
            {
                net.x=tx;
                net.y=ty;
                visfire[tx][ty]=1;//标记已烧过
                fire.push(net);//入队
                firetime[tx][ty]=firetime[now.x][now.y]+1;//时间加1
            }
        }
    }
}
void bfs()//人
{
    int f=0;
    while(!people.empty())
    {
        now=people.front();
        people.pop();
        if(now.x<=0||now.x>=n-1||now.y<=0||now.y>=m-1)//人走出来了
        {
            f=1;
            cout<<peopletime[now.x][now.y]+1<<endl;
            break;
        }
        for(int i=0; i<4; i++)//四种走法
        {
            net.x=now.x+dt[i][0];
            net.y=now.y+dt[i][1];
            if(net.x>=0&&net.x<n&&net.y>=0&&net.y<m&&!vispeople[net.x][net.y]&&mp[net.x][net.y]=='.'&&peopletime[now.x][now.y]+1<firetime[net.x][net.y])
            {
                vispeople[net.x][net.y]=1;//标记已走过
                people.push(net);//入队
                peopletime[net.x][net.y]=peopletime[now.x][now.y]+1;//时间+1
            }
        }
    }
    if(f==0)
        cout<<"IMPOSSIBLE"<<endl;
}
int main()
{
    cin>>T;
    while(T--)
    {
        MEM(firetime,INF);//初始化
        MEM(peopletime,INF);
        MEM(visfire,0);
        MEM(vispeople,0);
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]=='J')
                {
                    now.x=i;
                    now.y=j;
                    vispeople[i][j]=1;
                    people.push(now);
                    peopletime[i][j]=0;
                }
                if(mp[i][j]=='F')
                {
                    now.x=i;
                    now.y=j;
                    visfire[i][j]=1;
                    fire.push(now);
                    firetime[i][j]=0;
                }
            }
        }
        judgetime();
//        for(int i=0; i<n; i++)
//        {
//            for(int j=0; j<m; j++)
//            {
//                cout<<firetime[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        bfs();
        while(!fire.empty())//清空队列
        {
            fire.pop();
        }
        while(!people.empty())
        {
            people.pop();
        }
    }
}