题目大意:在一个迷宫内有k个火点,火会上下左右四处扩散/每秒,给出人的位置,人也会上下左右移动/每秒,问你人能不能在火没烧到人之前离开,如果可以输出最少离开需要的时间,如果不可以输出:“IMPOSSIBLE”。
思路:
因为可能不止只有一处火,需要用队列把火存起来,然后用两个数组存储人和火种到可以去的地方‘。’需要的时间,然后两个bfs就行了,第一个bfs存火种去各个地方的时间,第一个bfs找人去各个地方的时间是否小于火种。
代码:
#include<iostream>
#include<queue>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int person[maxn][maxn];
int maze[maxn][maxn];
char str[maxn][maxn];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct node{
int x,y;
node(int a,int b):x(a),y(b){}
node(){}
};
queue<node>st;
int line,column;
void bfs(){
while(!st.empty()){
node now=st.front();
st.pop();
for(int i=0;i<4;i++){
int fx=now.x+dir[i][0];
int fy=now.y+dir[i][1];
if(fx<0||fy<0||fx>=line||fy>=column)continue;
if(str[fx][fy]!='#'&&maze[fx][fy]==inf){
maze[fx][fy]=maze[now.x][now.y]+1;
st.push(node(fx,fy));
}
}
}
}
int personbfs(int x,int y){
queue<node>p;
p.push(node(x,y));
while(!p.empty()){
node now=p.front();
p.pop();
if(now.x==0||now.x==line-1||now.y==0||now.y==column-1){
return person[now.x][now.y]+1;
}
for(int i=0;i<4;i++){
int fx=now.x+dir[i][0];
int fy=now.y+dir[i][1];
if(fx<0||fy<0||fx>=line||fy>=column)continue;
if(str[fx][fy]!='#'&&person[fx][fy]==inf&&person[now.x][now.y]+1<maze[fx][fy]){
person[fx][fy]=person[now.x][now.y]+1;
p.push(node(fx,fy));
}
}
}
return -1;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int x,y;//bool flag=1;
scanf("%d%d",&line,&column);
for(int i=0;i<line;i++){
for(int j=0;j<column;j++){
person[i][j]=inf;
maze[i][j]=inf;
scanf(" %c",&str[i][j]);
if(str[i][j]=='J'){
person[i][j]=0;
x=i;y=j;
}else if(str[i][j]=='F'){
maze[i][j]=0;
st.push(node(i,j));
}
}
}
bfs();
int ans=personbfs(x,y);
if(ans==-1){
cout<<"IMPOSSIBLE"<<endl;
}else{
cout<<ans<<endl;
}
}
}