首页 > 其他分享 >12.石油储备(简单搜索 DFS/BFS 统计连通块个数)

12.石油储备(简单搜索 DFS/BFS 统计连通块个数)

时间:2023-05-02 21:12:06浏览次数:62  
标签:石油 12 int DFS st BFS 方格 油田 输入

石油储备

题目

一片土地可以看作是一个 \(n\) 行 \(m\) 列的方格矩阵。其中一些方格藏有石油,用 @ 表示,其余方格没有石油,用 * 表示。
每个方格都与其上、下、左、右、左上、右上、左下、右下八个方格视为相邻。
如果两个藏有石油的方格相邻,则它们被认为是处于同一片油田,否则它们被认为是处于不同油田。
请问,该土地中共有多少片油田。

输入格式

输入包含多组测试数据。
每组数据第一行包含两个整数 \(n,m\)
接下来 $ n$ 行,包含一个$ n$ 行 \(m\) 列的字符矩阵,表示土地情况。
当输入一行 0 0 时,表示输入结束。

输出格式

每组数据输出一行,一个整数,表示油田数量。

数据范围

最多包含 \(100\) 组数据。\(1≤n,m≤100\)

输入样例:

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

输出样例:

0
1
2
2

思路

\(floodfill\) 模型,搜索连通块,记录个数即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
char g[N][N];
int dx[]={-1,0,1,0,-1,-1,1,1};
int dy[]={0,1,0,-1,-1,1,-1,1};
bool st[N][N];
int n,m;
void dfs(int x,int y)
{
	st[x][y]=true;
	for(int i=0;i<8;i++)
	{
		int a=x+dx[i],b=y+dy[i];
		if(a<0||a>=n||b<0||b>=m||st[a][b]||g[a][b]=='*')continue;
		dfs(a,b);
	}
}
int main()
{
	while(cin>>n>>m,n&&m)
	{
		memset(st,0,sizeof st);
		for(int i=0;i<n;i++)cin>>g[i];
		
		
		int cnt=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(!st[i][j]&&g[i][j]=='@')dfs(i,j),cnt++;//统计连通块个数
		
		cout<<cnt<<endl;
	}
	
	return 0;
}

标签:石油,12,int,DFS,st,BFS,方格,油田,输入
From: https://www.cnblogs.com/zzmxj/p/17367568.html

相关文章

  • 14.找路(简单搜索 BFS 最短步数)
    找路↑题目链接题目给定一个\(n\)行\(m\)列的方格矩阵。其中有些方格是空地(可以进入),有些方格是餐厅(可以进入),有些方格是障碍(不可进入)。开始时,小\(Y\)和小\(M\)各自位于一个空地方格中。每个人都可以沿上下左右四个方向进行移动,移动一格距离需要花费\(11\)分钟时间。......
  • UVA 12177 First Knight
    (提醒:原题面是\(m\)行\(n\)列,这里改成了\(n\)行\(m\)列)首先很好想到设\(dp_{u,v}\)为\((u,v)\)的期望步数\(dp_{u,v}=\begin{cases}\sum_{i=1}^4dp_{u+du_i,v+dv_i}\timesp_i&(u\not=n\operatorname{or}v\not=m)\\0&(u=n\operator......
  • 9.点火游戏(简单搜索 BFS)
    点火游戏↑题目链接题目给定一个\(N\)行\(M\)列的方格矩阵。其中一部分方格是草地,其余部分是空地。草地能够被燃烧,空地不会。当某个草地在\(t\)时刻被点燃时,其上下左右四个方向的相邻方格中的草地方格也会在\(t+1\)时刻被点燃。注意,空地方格无论如何都不可能被点燃。......
  • 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\)毫升。可......
  • 12 ETH-美链
    《区块链技术与应用》课程链接:https://www.bilibili.com/video/BV1Vt411X7JF/?spm_id_from=333.337.search-card.all.click12ETH-美链目录12ETH-美链ICO(InitialCoinOffering)IPO(InitialPublicOffering)发布的代币没有自己的区块链,而是以智能合约的形式运行在以太坊的E......
  • 12 BTC-思考
    《区块链技术与应用》课程链接:https://www.bilibili.com/video/BV1Vt411X7JF/?spm_id_from=333.337.search-card.all.click12BTC-思考目录12BTC-思考哈希指针,比特币很多设计使用了hash指针,指针保存的只是本机的内存地址,发送到其他计算机上就没有意义,那么,在发布区块的时候,h......
  • 8.罐子(简单搜索 BFS最短步数+记录方案)
    罐子↑题目链接题目给你两个罐子,容积分别为\(A\)升和\(B\)升。现在,你可以进行如下三种操作:FILL(i),将罐子\(i(1≤i≤2)\)灌满水。DROP(i),将罐子\(i(1≤i≤2)\)清空。POUR(i,j),将罐子\(i\)中的水倒向罐子\(j\),直到罐子\(i\)空了或罐子\(j\)满了为止。请问,至少......
  • DFS找环,三色标记
    0代表还没访问1代表正在访问2代表已经访问完如果dfs过程中遇到1,则表明找到了环遇到2则不必继续找,用于剪枝https://blog.csdn.net/lj12358132134/article/details/80458349 ......
  • 7.洗牌(简单搜索 BFS)
    洗牌↑题目链接题目给定两叠纸牌\(S1\)和\(S2\),每叠恰好有\(C\)张牌。每张牌的尺寸大小都完全相同,但是颜色可能不同。下面介绍洗牌规则。不妨设\(S1\)中纸牌从上到下编号依次为\(a_1,a_2,…,a_C\),\(S_2\)中纸牌从上到下编号依次为\(b_1,b_2,…,b_C\)。洗牌就......