Demo entry 6762984

easy

   

Submitted by 反对法 on Oct 18, 2018 at 10:29
Language: C++. Code size: 819 Bytes.

/*
*** #18 统计联通域
*** dfs 
*/
#include <bits/stdc++.h>
#define llt long long 
using namespace std;

const int N=110;
char s[N][N];
int vis[N][N];//记录是否已经属于一个联通域
int n,m;

int offset[][2]={
	0,1,
	0,-1,
	1,0,
	-1,0,
	1,1,
	-1,-1,
	-1,1,
	1,-1
};

bool is_ok(int x,int y){// 判断是否越界
	return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x,int y){
	for(int i=0;i<8;++i){
		int xx=x+offset[i][0];
		int yy=y+offset[i][1];
		if(!is_ok(xx,yy)||s[xx][yy]!='#'||vis[xx][yy]) continue;
			// 已经越界,或者已经属于连通域 或者是个点
		vis[xx][yy]=true;
		dfs(xx,yy);
	}
}
int main(){

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%s",s[i]+1);
	int ans = 0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(s[i][j]=='#'&&!vis[i][j]){//没有连进连通域
				++ans;
				dfs(i,j);
			}
    cout<<ans<<endl;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).