UVA 11624 Fire(bfs + 多起点)

Love The Way You Lie 2024-02-17 19:09 27阅读 0赞

题意：给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;
    }