蓝桥杯2023年第十四届省赛真题-岛屿个数_蓝桥杯eda十四届省赛题

目录

题目

题目描述

输入格式

输出格式

样例输入

样例输出

思路：两次DFS（染色法+合并）-Dotcpp编程社区

代码：

---

题目

题目描述

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。

在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)，其中(x(i+1)%k , y(i+1)%k) 是由 (xi , yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)，

此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

输入格式

第一行一个整数 T，表示有 T 组测试数据。

接下来输入 T 组数据。对于每组数据，第一行包含两个用空格分隔的整数M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是‘0’ 或 ‘1’。

输出格式

对于每组数据，输出一行，包含一个整数表示答案。

样例输入

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

样例输出

1
3

思路：两次DFS（染色法+合并）-Dotcpp编程社区

1. 首先我们用一个比地图大一圈的矩阵来存储这个地图（只需要大一圈就行，数组这样开sea[52][52]）
2. 由于地图外都是海水，所以先所有点都初始化为0（注意是字符’0’）
3. 然后，我们从(0,0)开始把所有相连的海水都标记为2（第一次DFS），这个过程之后图中所有剩下没有被更改的0一定在岛屿内部，（这次搜索要八连通，请读者自己思考为什么）；
4. 接下来我们再遍历一遍地图，把所有0都变成1，这样岛屿和其内部的子岛屿就“合为一体”了（请读者仔细分析）；
5. 所以，剩下来的问题就是上面那个更简单的问题了。（第二次DFS）

以上3，4，点为关键点，以下代码的总体思路是一样的，实现时，将两个dfs函数合在一起了

代码：

#include<iostream>
using namespace std;
typedef long long itn;
//数据范围
//输出格式
//i,j,x,y写错
//scanf("%lld",&a); 忘加&
int a[55][55];
int f[55][55];
int n,m;
int dx[9]={0,1,-1,0,-1,1,1,-1};
int dy[9]={1,0,0,-1,-1,1,-1,1};
 
 
//x，y：从a[x][y],开始      
//nx，ny： 搜索的范围是nx*ny   
//flag：如果格子是flag，就跳过，不经过这个格子 
//fw：fw==8：上下左右以及四个斜方向      fw==4：  上下左右 
//此函数为将nx*ny的地图染成-1，除了陆地，也就是1 
 
void dfs1(int x,int y,int nx,int my,int flag,int fw) 
{
	for(int i=0;i<fw;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<0||yy<0||xx>nx||yy>my||a[xx][yy]==-1||a[xx][yy]==flag) continue;
		a[xx][yy]=-1;
		dfs1(xx,yy,nx,my,flag,fw);
	}
}
 
 
void mymain()
{
	//输入 
	int ans=0;cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			char ch;cin>>ch;
			if(ch=='\n') continue;
			a[i][j]=ch-'0';
		}
	//0，0：从a[0][0],开始      
	//52，52： 搜索的范围是52*52   
	//1：如果格子是1，跳过 
	//8：上下左右以及四个斜方向  
	
	//将岛屿(1)之外的水(0)全部变成-1 ,环形岛内的水(0)无法变成-1； 
	dfs1(0,0,52,52,1,8);
 
	//将环形岛内的水(0)变成岛屿(1) 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==0) a[i][j]=1;
		}
	}
	
	//如果该格子是岛屿(1)，答案(ans) 加一，并将该岛屿(1)全部变为-1 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==1) 
			{
				ans++;
				a[i][j]=-1;
				dfs1(i,j,n,m,-1,4);//4：上下左右 
			}
		}
	}
	//输出答案 
	cout<<ans<<"\n";
}
 
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t; 
	while(t--)
	{
		for(int i=0;i<=54;i++)
		for(int j=0;j<=54;j++)
		{
			a[i][j]=0;
		}
		mymain();
	}
 	return 0;
}