Time Limit: 5000MS | Memory Limit: 262144KB | 64bit IO Format: %lld & %llu |
Description
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
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 the input.
Output
Sample Input
Case #1:
4 4
####
#JF#
#..#
#..# Case #2:
3 3
###
#J.
#.F
Sample Output
3
IMPOSSIBLE
Source
题目本身不难,但是很容易WA,两个坑点:一开始就在边界的情况和火堆根本碰不到人的情况,第一种稍微把BFS判断顺序改一下就可以了,第二种会导致比较人和火谁先跑出迷宫这种BFS方法WA,可以假设若火根本碰不到人,那么就算火跑的比香港记者更快,那人还是可以走出去的,然后怎么保证每一个地方都是最早被火碰到的呢?把所有的火都压入队列一次性BFS掉,这样保证层数相同时时间可以统一更新,因此要用另一种保险的BFS方法,把每一个点时间设好,再对人进行BFS,被这两个坑点弄的WA十余次………哎还是too
naive。找了个只是输出格式修改了的题面放上去,方便起见自己把输出格式也改成了原题一样的……
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0); const int N=1010;
struct info
{
int x;
int y;
int t;
info operator+(info b)
{
b.x+=x;
b.y+=y;
b.t+=t;
return b;
}
};
info J,F,direct[4]={{1,0,1},{-1,0,1},{0,1,1},{0,-1,1}};
char pos[N][N];
int firetime[N][N];
int vis[N][N];
int n,m;
queue<info>Q;
inline bool checkfire(const info &f)
{
return (f.x>=0 && f.x<n && f.y>=0 && f.y<m && pos[f.x][f.y]!='#' && vis[f.x][f.y]==0);
}
inline bool checkman(const info &a)
{
return (a.x>=0 && a.x<n && a.y>=0 && a.y<m && pos[a.x][a.y]!='#' && pos[a.x][a.y]!='F' && vis[a.x][a.y]==0);
}
inline void init()
{
MM(pos,0);
MM(firetime,INF);
J.x=-1,J.y=-1,J.t=-1;
while (!Q.empty())
Q.pop();
}
inline void setfire()
{
MM(vis,0);
while (!Q.empty())
{
info now=Q.front();
Q.pop();
for (int i=0; i<4; ++i)
{
info v=now+direct[i];
if(checkfire(v))
{
vis[v.x][v.y]=1;
firetime[v.x][v.y]=v.t;
Q.push(v);
}
}
}
}
inline int run(const info &s)
{
MM(vis,0);
queue<info>q;
vis[s.x][s.y]=1;
q.push(s);
while (!q.empty())
{
info now=q.front();
q.pop();
if(now.x==0||now.x==n-1||now.y==0||now.y==m-1)
return now.t;
for (int i=0; i<4; ++i)
{
info v=now+direct[i];
if(checkman(v)&&v.t<firetime[v.x][v.y])
{
vis[v.x][v.y]=1;
q.push(v);
}
}
}
return -1;
}
int main(void)
{
int tcase,i,j,out,cnt;
scanf("%d",&tcase);
while (tcase--)
{
init();
cnt=0;
out=-1;
scanf("%d%d",&n,&m);
for (i=0; i<n; ++i)
{
scanf("%s",pos[i]);
for (j=0; j<m; ++j)
{
if(pos[i][j]=='J')
{
J.x=i;
J.y=j;
J.t=0;
}
else if(pos[i][j]=='F')
{
F.x=i;
F.y=j;
F.t=0;
Q.push(F);
}
}
}
setfire();
out=run(J);
out==-1?puts("IMPOSSIBLE"):printf("%d\n",out+1);
}
return 0;
}