统计连通域(DFS)

题目描述

享有长沙界小达芬奇称号的磊哥又在认真画图，他用'#'、‘.’画了一个长方形，另有长沙小图灵美誉的他

思考：一个#号八个方向中存在#号，即称得上两个#是相连的。相连是可以传递的。所有相连的#回合成

一个连通域，他想统计出连通域的个数。

.? .? .? .? .? .
.? .? #? .? .? .
.? .? .? .? .? .
.? #? #? #? .? .
.? #? .? #? .? .
.? #? #? #? .? .

上面第二行第3列的#形成一个连通域。下面三行#号形成一个连通域。

输入

第一行输入两个整数：n，m 表示长方形行数和列数。
下面输入n行，每行有m个字符(无空格分隔) .
字符‘#’ 或者 ‘.’。

输出

输出整数表示连通域的个数。

样例输入?Copy

12 12
.##########.
#..........#
#..#...##..#
#.##..#..#.#
#......#.#.#
#....#..#..#
#...#.#....#
#..#...#...#
.#..#.#....#
#....#.....#
#.........#.
.#########..

样例输出?Copy

4

提示

100%的数据满足：1 ≤ n,m ≤ 100.

代码实现：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
char a[110][110];
int m,n;
int dx[10]={0,-1,-1,-1,0,0,1,1,1};
int dy[10]={0,-1,0,1,-1,1,-1,0,1};
void dfs(int x,int y)
{
	int xx,yy;
	a[x][y]='.';
	for(int t=1;t<=8;t++)
	{
		xx=x+dx[t];
		yy=y+dy[t];
		if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]=='.')
		{
			continue;
		}
		dfs(xx,yy);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
			{
			 	cnt++;
			 	dfs(i,j);
			}
		}
	}
	cout<<cnt;
	return 0;	
}