UVA 11624 Fire!(双点bfs)

       这道题就是问一个人能否逃出地图，当然不是那种简单的走地图，还有一堆火(划重点)。说下思路，这道题坑点还是比较多的，首先火源不只一处，可以有多处，那么我们就要把每处火都记录下来，然后bfs搜索前让火源全部入队，还有就是不需要逃出地图，只要跑到边界就ok。(说是双点bfs，其实就是把火和人都塞进队列里乱搜一通

AC代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 1005;
struct Node{
	int x,y,step;
	bool pf;          // 标记是人还是火
}fire_num[MAXN],Now,Next;    //因为有多个火源，所以fire用数组
char MAP[MAXN][MAXN];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,T,k;

int bfs(){
	queue<Node> q;
	for(int i=0;i<k;i++){       //火源入队
		q.push(fire_num[i]);
	}
	q.push(Now);
	while(!q.empty()){
	 Now = q.front();
		q.pop();
		if(Now.pf==1&&(Now.x==0||Now.y==0||Now.x==n-1||Now.y==m-1)){
			return Now.step+1;
		}
		for(int i=0;i<4;i++){
			Next.x = Now.x + dir[i][0];
			Next.y = Now.y + dir[i][1];
			if(Next.x >= 0 && Next.y >= 0 && Next.y < m && Next.x < n && MAP[Next.x][Next.y] != '#'){
				MAP[Next.x][Next.y] = '#';
				Next.step = Now.step + 1;
				Next.pf = Now.pf;
				q.push(Next);
			}
		}
	}
	return -1;
}

int main()
{
   scanf("%d",&T);
   while(T--){
      scanf("%d%d",&n,&m);
      for(int i=0;i<n;i++){
	scanf("%s",MAP[i]);
      }
      k = 0;
      for(int i=0;i<n;i++){
	for(int j=0;j<m;j++){
	    if(MAP[i][j]=='J'){
		Now.x = i;
		Now.y = j;
		Now.pf = 1;
		Now.step = 0;
	     }
	    if(MAP[i][j]=='F'){
		fire_num[k].x = i;
		fire_num[k].y = j;
	        fire_num[k].step = 0;
	        fire_num[k++].pf = 0;
	    }
	}
   }
   int temp = bfs();
   if(temp==-1){
	printf("IMPOSSIBLE\n");
   }
   else{
	printf("%d\n",temp);
   }
 }
  return 0;
}
/*
   [来源] UVA 11624
   [题目]
      Fire!
   [题意]
      一个人额一堆火的问题，看人是否能逃出迷宫(达到地图边缘)，注意火源不止一个(双点BFS)。
   [输入]
      2
      4 4
      ####
      #JF#
      #..#
      #..#
      3 3
      ###
      #J.
      #.F
   [输出]
      3
      IMPOSSIBLE
*/