和普通BFS相比 多了个火
那么先对火做一次BFS 预处理每个格子着火的时间
偷懒了 少开个数组 然后错了半天
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
const int MAX = 1010;
char a[MAX][MAX];
int map[MAX][MAX];
struct node
{
int x;
int y;
int t;
}s;
int n, m;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
bool bfs()
{
queue <node> f;
queue <node> q;
memset(map,-1,sizeof(map));
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
{
if(a[i][j] == ‘F‘)
{
node t;
t.x = i;
t.y = j;
t.t = 0;
f.push(t);
map[i][j] = 0;
}
else if(a[i][j] == ‘J‘)
{
node t;
t.x = i;
t.y = j;
t.t = 0;
q.push(t);
}
}
}
while(!f.empty())
{
node u = f.front();
f.pop();
for(i = 0; i < 4; i++)
{
node t;
t.x = u.x + dir[i][0];
t.y = u.y + dir[i][1];
t.t = u.t + 1;
if(t.x >= 0 && t.x < n && t.y >= 0 && t.y < m && a[t.x][t.y] != ‘#‘ && map[t.x][t.y] == -1)
{
map[t.x][t.y] = t.t;
f.push(t);
}
}
}
/*for(i = 0;i < n; i++)
{
for(j = 0;j < m; j++)
printf("%d ",map[i][j]);
puts("");
}*/
while(!q.empty())
{
node u = q.front();
q.pop();
for(i = 0; i < 4; i++)
{
node t;
t.x = u.x + dir[i][0];
t.y = u.y + dir[i][1];
t.t = u.t + 1;
if(t.x < 0 || t.x >= n || t.y < 0 || t.y >= m)
{
printf("%d\n",t.t);
return true;
}
if(t.x >= 0 && t.x < n && t.y >= 0 && t.y < m && a[t.x][t.y] != ‘#‘ && (map[t.x][t.y] > t.t || map[t.x][t.y] == -1))
{
a[t.x][t.y] = ‘#‘;
q.push(t);
}
}
}
return false;
}
int main()
{
int cas;
int i, j;
scanf("%d",&cas);
while(cas--)
{
scanf("%d %d",&n,&m);
for(i = 0; i < n; i++)
scanf("%s",a[i]);
if(!bfs())
printf("IMPOSSIBLE\n");
}
return 0;
}