UVA 11624 Fire(bfs + 多起点)

题意：给1个n*m的网格，上面有的点能走，有的点不能走（墙），然后有的点是火源，火源和人一样，每次都是上下左右四个方向蔓延，速度一样是1，火也不可以从墙上跨过去，给你人的起点，终点是只要走到边界就行，就是走出矩阵，问你最小逃生时间。

思路：需要注意一点是，火源不止一个；首先将所有火结点加入容器（vector），调用bfs时先将火结点加入队列，其他的和普通bfs就没什么区别了。

AC代码如下：

#include<cstdio>#include<queue>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int maxn=1000+10;struct node{	int x,y;	int c;     //0表示人、1表示火 	node(int x=0,int y=0,int c=0):x(x),y(y),c(c){}}nj,nf;int d[maxn][maxn];char g[maxn][maxn];vector<node>vec;   //储存火结点 int R,C;int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};bool isValid(node &nd){	return nd.x>=0&&nd.x<R && nd.y>=0&&nd.y<C;}void bfs(){	memset(d,0,sizeof(d));	queue<node>q;	for(int i=0;i<vec.size();i++){   //先将所有的火结点加入队列 		q.push(vec[i]);		d[vec[i].x][vec[i].y]=1;	}	q.push(nj);      //再加入人 	d[nj.x][nj.y]=1;	while(!q.empty()){		node u=q.front();		q.pop();		if(u.x==0 || u.x==R-1 || u.y==0 || u.y== C-1)//如果到边界了 					if(g[u.x][u.y]=='.' && u.c==0){						PRintf("%d/n",d[u.x][u.y]);						return ;					}		for(int i=0;i<4;i++){			node v=node(u.x+dir[i][0],u.y+dir[i][1],u.c); 			if(isValid(v) && !d[v.x][v.y] && g[v.x][v.y]=='.' ){				q.push(v);				d[v.x][v.y]=d[u.x][u.y]+1;			}		}	}	printf("IMPOSSIBLE/n");}int main(){	int T;	scanf("%d",&T);	while(T--){		scanf("%d%d",&R,&C);		getchar();		for(int i=0;i<R;i++){			for(int j=0;j<C;j++){				scanf("%c",&g[i][j]);				if(g[i][j]=='J'){nj.x=i;nj.y=j;nj.c=0;}				if(g[i][j]=='F'){nf.x=i;nf.y=j;nf.c=1;vec.push_back(nf);}			}			getchar(); //吃掉换行 		} 		if(nj.x==0 || nj.x==R-1 || nj.y==0 || nj.y==C-1)printf("1/n");  //如果在边界处 		else bfs();		vec.clear();            	}	return 0;}