【UVA - 11624】Fire!
【UVA – 11624】Fire!
–>Fire!
直接上中文
Descriptions:
- 乔在迷宫中工作。不幸的是,迷宫的一部分着火了,迷宫的主人没有制定火灾的逃跑计划。请帮
助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火,你必须确定火焰烧到他之前,
乔是否可以离开迷宫,如果能离开他能跑多快。- 乔和火每分钟移动一个方格,上、下、左、右,四个方向中的一个。火势向四个方向同时蔓延。
乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。
输入
- 第一行输入包含一个整数,即测试次数
- 每个测试用例的第一行包含两个
- 整数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();
- }
- }
- }