首页 > 其他分享 >9.点火游戏(简单搜索 BFS)

9.点火游戏(简单搜索 BFS)

时间:2023-05-02 19:00:29浏览次数:49  
标签:Case ... 点火 int 草地 点燃 BFS 搜索 方格

点火游戏

↑ 题目链接

题目

给定一个 \(N\) 行 \(M\) 列的方格矩阵。其中一部分方格是草地,其余部分是空地。草地能够被燃烧,空地不会。当某个草地在 \(t\) 时刻被点燃时,其上下左右四个方向的相邻方格中的草地方格也会在 \(t+1\) 时刻被点燃。
注意,空地方格无论如何都不可能被点燃。
现在,你可以选择最多两个草地,将它们点燃。
请你计算,使得所有草地都被点燃所需花费的最少时间。

输入格式

第一行包含整数 \(T\) ,表示共有 \(T\)组测试数据。
每组数据第一行包含两个整数 \(N,M\)
接下来 \(N\) 行,包含一个 \(N×M\) 的字符矩阵,# 表示草地,. 表示空地。

输出格式

每组数据输出一个结果,每个结果占一行。
结果表示为 Case x: y,其中 \(x\) 为组别编号(从 \(1\) 开始),\(y\) 点燃所有草地需要花费的最短时间。如果无法点燃所有草地或者所有方格都是空地则输出 −1

数据范围

\(1≤T≤100,1≤N,M≤10\)

输入样例:

5
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#
3 3
...
...
...

输出样例:

Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2
Case 5: -1

思路

枚举两个起点入队,在 \(BFS\) 搜索过程中更新最值即可

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=15;
char g[N][N];
int d[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m;
int cnt;
int maxv;

void bfs(int sx1,int sy1,int sx2,int sy2)
{
	memset(d,-1,sizeof d);
	
	queue<PII>q;
	
	q.push({sx1,sy1});
	q.push({sx2,sy2});
	d[sx1][sy1]=0;
	d[sx2][sy2]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		cnt++;//统计草地个数
		for(int i=0;i<4;i++)
		{
			int a=t.x+dx[i],b=t.y+dy[i];
			if(a<0||a>=n||b<0||b>=m||d[a][b]!=-1||g[a][b]=='.')continue;
			d[a][b]=d[t.x][t.y]+1;
			maxv=max(d[a][b],maxv);//每次搜索取距离最大值
			q.push({a,b});
		}
	
	}
	
}



int main()
{
	int T;
	cin>>T;
	
	for(int Case=1;Case<=T;Case++)
	{
		cin>>n>>m;
		
		vector<PII>grass;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
			{
				cin>>g[i][j];
				if(g[i][j]=='#')grass.push_back({i,j});	
			}
		
		
		int res=1e9;
		if(grass.size()==1)res=0;//特判草地数量为1
		
		//枚举两块草地
		for(int i=0;i<grass.size();i++)
			for(int j=i+1;j<grass.size();j++)
				{
					int sx1=grass[i].first,sy1=grass[i].second;
					int sx2=grass[j].first,sy2=grass[j].second;
					
					cnt=0,maxv=0;
					bfs(sx1,sy1,sx2,sy2);
					
					if(cnt==grass.size())
					    res=min(res,maxv);//所有情况取最小值
					
					
					
				}
		
		if(res==1e9)res=-1;
		
		printf("Case %d: %d\n",Case,res);
		
	}
	
	return 0;
}

标签:Case,...,点火,int,草地,点燃,BFS,搜索,方格
From: https://www.cnblogs.com/zzmxj/p/17368053.html

相关文章

  • 11.迷宫问题(BFS 储存路径)
    迷宫问题↑题目链接题目给定一个\(n×n\)的二维数组,如下所示:intmaze[5][5]={0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,};它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上......
  • 13.非常可乐(简单搜索 BFS)
    非常可乐题目大家一定觉的运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是\(N\)毫升和\(M\)毫升。可......
  • 8.罐子(简单搜索 BFS最短步数+记录方案)
    罐子↑题目链接题目给你两个罐子,容积分别为\(A\)升和\(B\)升。现在,你可以进行如下三种操作:FILL(i),将罐子\(i(1≤i≤2)\)灌满水。DROP(i),将罐子\(i(1≤i≤2)\)清空。POUR(i,j),将罐子\(i\)中的水倒向罐子\(j\),直到罐子\(i\)空了或罐子\(j\)满了为止。请问,至少......
  • 7.洗牌(简单搜索 BFS)
    洗牌↑题目链接题目给定两叠纸牌\(S1\)和\(S2\),每叠恰好有\(C\)张牌。每张牌的尺寸大小都完全相同,但是颜色可能不同。下面介绍洗牌规则。不妨设\(S1\)中纸牌从上到下编号依次为\(a_1,a_2,…,a_C\),\(S_2\)中纸牌从上到下编号依次为\(b_1,b_2,…,b_C\)。洗牌就......
  • 3.抓住那头牛(简单搜索 BFS)
    抓住那头牛↑题目链接题目农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点\(N\),牛位于点\(K\)。农夫有两种移动方式:从\(X\)移动到\(X−1\)或\(X+1\),每次移动花费一分钟从\(X\)移动到\(2∗X\),每次移动花费一分钟假设牛没有意识到农夫的行动,站......
  • 2.地牢大师(简单搜索 BFS)
    地牢大师↑题目链接题目你现在被困在一个三维地牢中,需要找到最快脱离的出路!地牢由若干个单位立方体组成,其中部分不含岩石障碍可以直接通过,部分包含岩石障碍无法通过。向北,向南,向东,向西,向上或向下移动一个单元距离均需要一分钟。你不能沿对角线移动,迷宫边界都是坚硬的岩石,你......
  • 1.棋盘问题(简单搜索)
    棋盘问题↑题目链接题目在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放\(k\)个棋子的所有可行的摆放方案数目\(C\)输入格式输入含有多组测试数据。......
  • pyqt5-文本框搜索功能
    1、介绍作用是对一个文本框组件的文本进行搜索,将搜索结果在文本框中进行字体颜色标记,允许re或者普通文本搜索,支持上一个或下一个的跳转,支持标签显示当前索引和总个数。2、ui3、代码(1)自定义search.py,其中包含两个重要的函数"""搜索算法返回结果是list,元素是二元list,表示......
  • 堆与二叉搜索树学习笔记
    部分内容来自OI-WIKI。1.堆堆的定义堆是一棵二叉树,满足每个节点的键值都大于等于它的父亲节点或者小于等于它的父亲节点。每个节点的键值都大于等于它的父亲节点的叫小根堆,每个节点的键值都小于等于它的父亲节点的叫大根堆。优先队列是一种抽象数据类型,它是一种容器,里面有......
  • BFS 简单应用
    前言:BFS即广度优先搜索(或宽度优先搜索),具体定义和实现不在赘述。本文所有代码前的开头头文件,宏定义和命名空间如下(只是一些常用的define和一个快读):#include<bits/stdc++.h>#defineTptemplate<typenameTy>#defineTstemplate<typenameTy,typename...Ar>#definell......