首页 > > 程序设计 > C/C++ >

J - Fire! UVA - 11624

2018-09-01 05:38:15来源：博客园阅读 ()

Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze.

Given Joe’s location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it.

Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.

Input

The first line of input contains a single integer, the number of test
cases to follow. The first line of each test case contains the two
integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The
following R lines of the test case each contain one row of the maze. Each of these lines contains exactlyC characters, and each of these characters is one of:

? #, a wall
? ., a passable square
? J, Joe’s initial position in the maze, which is a passable square? F, a square that is on fire

There will be exactly one J in each test case.Output

For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

Sample Input

4 4

####

#JF#

#..#

3 3

###

#J.

#.F

Sample Output

IMPOSSIBLE

题意：

题目：一个平面迷宫中有一个人，迷宫中有些点起火了，火和人每个单位时间只能向相邻的格子移动，其中有一些空间被墙壁占据，问这个人在不被烧到的情况下，离开迷宫的最快时

思路：明显是一个搜索题，但是怎么搜呢？可以先把所有的格子都扫一遍，然后把带火的先放到队列里面，最后再把J放进队列，这样就可以保证在同一秒的时候是火先蔓延了，之后人才再可以走的地方走路，在火蔓延的时候记得把火的性质传递过去，我是用了一个id，id为0表示是火，那么火蔓延的时候把id给传下去就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
#define _e exp(1.0)
#define ll long long
int const maxn = 1005;
const int mod = 1e9 + 7;
int gcd(int a, int b) {
    if (b == 0) return a;  return gcd(b, a % b);
}
struct node
{
    int x,y,t,id;
};
int n,m,ans,sum;
int vis[maxn][maxn];
char map[maxn][maxn];
queue<node>que;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
bool judge(int x,int y)
{
    if(x>=0 && x<n && y>=0 && y<m && !vis[x][y])  //如果在地图中并且没有被走过就返回true，我把'#'也当作走过了就不需要判断#了
        return true;
    return false;
}

int bfs()
{
    node next;
    while(!que.empty())
    {
        node p=que.front();
        que.pop();
        for(int i=0;i<4;i++)
        {
            next.x=p.x+dx[i];
            next.y=p.y+dy[i];
            next.t=p.t+1;
            next.id=p.id;  //把火和没有火的的性质蔓延下去
            if(next.id==1 && (next.x==-1 || next.x==n || next.y==-1 || next.y==m))  //如果到了边界并且id还是1表示没有被烧过就可以返回时间t了
               return next.t;
            if(judge(next.x,next.y))
            {
                vis[next.x][next.y]=1;
                que.push(next);
            }
               
        }
    }
    return -1;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        node s1,s2;
        scanf("%d%d",&n,&m);
        while(!que.empty())
            que.pop();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>map[i][j];
                if(map[i][j]=='.')
                    vis[i][j]=0;
                else if(map[i][j]=='#')
                    vis[i][j]=1;
                else if(map[i][j]=='F')  //记录这是一个火，id为0表示这是一个火
                {
                    vis[i][j]=1;
                    s1.x=i;  s1.y=j;
                    s1.t=0;  s1.id=0;
                    que.push(s1);
                }
                else if(map[i][j]=='J')
                {
                    vis[i][j]=1;
                    s2.x=i;  s2.y=j;
                    s2.t=0;  s2.id=1;
                }
            }
        }
        que.push(s2);    //先把所有的火都push进去再push人，可以保证在同一秒的时候是火先走，那人只能走不是火的地方，不然就火就和人相遇了
        int ans=bfs();
        if(ans==-1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n",ans);
    }
    return 0;
}