【J - Fire!】

思路：

• 自己想出来豆
• BFS
• 使用两个列表分别记录火的状态和人的状态，先火再人，并且使用火的新状态来对人剪枝。

代码：

• 210ms

​//210ms


#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 1005;
const int moveto[4][2] = {1,0 , -1,0 , 0,1 , 0,-1};

int M,N;
int ans;
char mp [maxn][maxn];
bool vis[maxn][maxn];
struct Joe{
	int x , y;
	int step;
	Joe(int x,int y,int step) : x(x) , y(y) , step(step) {} ;
};
struct Fire{
	int x,y;
	Fire(int x,int y) : x(x) , y(y) {} ;
};
queue<Joe>  Qj;
queue<Fire> Qf;

void init(){
	ans = 0;
	memset(vis , false , sizeof(vis));
	while(Qj.size())
		Qj.pop();
	while(Qf.size())
		Qf.pop();
	return ;
}

void bfs(){
	while(Qj.size()){
		int fnum = Qf.size();
		int jnum = Qj.size();
		for(int i=1;i<=fnum;i++){
			Fire cur = Qf.front();Qf.pop();
			int x = cur.x;
			int y = cur.y;
			for(int i=0;i<4;i++){
				int nx = x + moveto[i][0];
				int ny = y + moveto[i][1];
				if(vis[nx][ny])
					continue;
				if(nx < 1 || nx > M || ny < 1 || ny > N)
					continue;
				vis[nx][ny] = true;
				Qf.push(Fire(nx,ny));
			}
		}
		for(int i=1;i<=jnum;i++){
			Joe cur = Qj.front();Qj.pop();
			int x = cur.x , y = cur.y ;
			for(int i=0;i<4;i++){
				int nx = x + moveto[i][0];
				int ny = y + moveto[i][1];
				if(vis[nx][ny])
					continue;
				vis[nx][ny] = true;
				Qj.push(Joe(nx , ny , cur.step + 1));
				if(nx < 1 || nx > M || ny < 1 || ny > N){
					ans = cur.step + 1;
					return ;
				}
			}
		}
	}
	return ;
}

int main(){
	int T;cin>>T;
	while(T--){
		init();
		cin>>M>>N;
		for(int i=1;i<=M;i++)
			for(int j=1;j<=N;j++){
				cin>>mp[i][j];
				if(mp[i][j] == '#')
					vis[i][j] = true;
				if(mp[i][j] == 'J')
					Qj.push(Joe(i,j,0)) , vis[i][j] = true;
				if(mp[i][j] == 'F')
					Qf.push(Fire(i,j))  , vis[i][j] = true;
			}
		bfs();
		if(ans)
			cout<<ans<<endl;
		else
			cout<<"IMPOSSIBLE"<<endl;
	}
	return 0;
}​