FZU 2150 Fire Game(双端bfs搜索)

小灰灰 2024-02-17 19:09 36阅读 0赞

题意：给你块地，有空地，也有草堆，让你选两个草堆进行点火，燃烧的草堆会引燃上下左右的相邻草堆，每一次引燃花费1s时间，问你最少花多长时间把草堆都点着，如果做不到输出-1.

思路：每次枚举两块草坪，两端同时bfs（也就是说一开始加入两个节点到队列当中，和以前的类型一个道理没什么区别），用变量count1计算草坪个数，当count1减小到0时，即找到了本次枚举的解，并在节点node中设置一变量为c记录当前状态草坪个数（用于返回结果的判断）。

AC代码如下：

#include<cstdio>
    #include<queue>
    #include<vector> 
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10+2;
    struct node{
    	int x,y;
    	int c;   //当前状态下草坪的剩余数量 
    	node(int x=0,int y=0,int c=0):x(x),y(y),c(c){}
    }; 
    int n,m;
    int count1;    //草坪数量 
    char g[maxn][maxn];  
    int d[maxn][maxn];
    int dir[][2]={
       {0,1},{0,-1},{1,0},{-1,0}};
    bool isValid(node &nd){
    	return nd.x>=0&&nd.x<n && nd.y>=0&&nd.y<m;
    }
    int bfs(node &n1,node &n2){
    	int t=count1;            //要保证每次枚举草坪的数量不会被改变 
    	memset(d,-1,sizeof(d));
    	queue<node>q;
    	n1.c=--t;
    	q.push(n1);
    	n2.c=--t;
    	q.push(n2);
    	d[n1.x][n1.y]=0;
    	d[n2.x][n2.y]=0;
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(!u.c){         //当草坪的数量为零时说明已经燃烧完了 
    		return d[u.x][u.y];}
    		for(int i=0;i<4;i++){
    			node v=node(dir[i][0]+u.x,dir[i][1]+u.y,0);
    			if(isValid(v) && d[v.x][v.y]==-1 && g[v.x][v.y]=='#'){
    			    v.c=--t;
    				q.push(v);
    				d[v.x][v.y]=d[u.x][u.y]+1;
    			}
    		}
    	}
    	return -1;
    }
    int main(){
    	int T;
    	scanf("%d",&T); 
    	int flag=0;
    	while(T--){
    		scanf("%d%d",&n,&m);
    		for(int i=0;i<n;i++)scanf("%s",g[i]);
    		count1=0;
    		vector<node>vec;
    		for(int i=0;i<n;i++)
    			for(int j=0;j<m;j++)
    				if(g[i][j]=='#'){
    					vec.push_back(node(i,j,0));
    					count1++;
    				}
    		if(vec.size()>2){	int min1=10000;      //当草坪数量<=2时直接输出0，否则每次枚举两个草坪 
    		for(int i=0;i<vec.size();i++){
    			for(int j=i+1;j<vec.size();j++){
    					int temp=bfs(vec[i],vec[j]);
    					if(temp!=-1){
    						min1=min(min1,temp);
    					}
    			}
    		}
    		if(min1==10000)printf("Case %d: -1\n",++flag);
    		else printf("Case %d: %d\n",++flag,min1);
      }else printf("Case %d: 0\n",++flag);
    	}
    	return 0;
    }