和普通BFS相比 多了个火
那么先对火做一次BFS 预处理每个格子着火的时间
偷懒了 少开个数组 然后错了半天
#include
#include
#include
#include
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 = {1,0,-1,0,0,1,0,-1};
bool bfs（）
{
queue f;
queue 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] ;
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] ;
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;
} |