J - Fire!---UVA 11624

时间:2022-12-16 22:59:11

题目链接

题意:J代表Joe的位置,F代表火的起点,下一刻火将会向四周扩散,求Joe逃离的最短时间,如果不能逃离输出IMPOSSIBLE;

注意火的起点可能不止一处

可以用两次bfs分别求出人到达某个位置所用时间和火到达某个位置所用时间

 #include<iostream>
#include<stdio.h>
#include<string.h>
#define INF 0xfffffff
#include<queue>
#include<algorithm>
using namespace std;
#define N 1010 int dir[][]={ {,},{-,},{,-},{,} };
char map[N][N];
int people[N][N], fire[N][N];//分别代表人和火到达该位置的时间;
int n, m, k, vis[N][N];
struct node
{
int x,y;
}f[N*N];//火的位置;可能不止一处; void FireBfs()
{
queue<node> Q;
node p, q;
memset(vis, , sizeof(vis));
memset(fire, -, sizeof(fire));
for(int i=; i<k; i++)
{
Q.push(f[i]);
fire[f[i].x][f[i].y] = ;
vis[f[i].x][f[i].y]=;
}
while(Q.size())
{
p = Q.front(); Q.pop();
for(int i=; i<; i++)
{
q.x=p.x+dir[i][];
q.y=p.y+dir[i][];
if(q.x>= && q.y>= && q.x<n && q.y<m && vis[q.x][q.y]== && map[q.x][q.y]!='#')
{
fire[q.x][q.y] = fire[p.x][p.y] + ;
vis[q.x][q.y] = ;
Q.push(q);
}
}
}
}
int PeopleBfs(node s)
{
queue<node> Q;
node p, q;
memset(vis, , sizeof(vis));
memset(people, -, sizeof(people));
Q.push(s);
people[s.x][s.y] = ;
vis[s.x][s.y] = ;
while(Q.size())
{
p = Q.front(); Q.pop();
if(p.x==||p.x==n-||p.y==||p.y==m-)
{
if((people[p.x][p.y] != - && people[p.x][p.y]<fire[p.x][p.y]) || (people[p.x][p.y] != -&&fire[p.x][p.y] == -) )//能到达边界并且在火到达之前;
return people[p.x][p.y];
} for(int i=; i<; i++)
{
q.x = p.x + dir[i][];
q.y = p.y + dir[i][];
if(q.x>= && q.x<n && q.y>= && q.y<m && vis[q.x][q.y]== && map[q.x][q.y]!='#')
{
people[q.x][q.y] = people[p.x][p.y] + ;
vis[q.x][q.y] = ;
Q.push(q);
}
}
}
return -;
}
int main()
{
int T; scanf("%d", &T);
while(T--)
{
node J;
scanf("%d%d", &n, &m);
k = ;
for(int i=; i<n; i++)
{
scanf("%s", map[i]);
for(int j=; j<m; j++)
{
if(map[i][j]=='J')
J.x = i, J.y = j;
if(map[i][j]=='F')
f[k].x = i,f[k++].y = j;
}
}
FireBfs();
int ans = PeopleBfs(J);
if(ans==-)
printf("IMPOSSIBLE\n");
else
printf("%d\n", ans);
}
return ;
}