题目描述

C⽼师名下的资产有⼀座⼩岛。在这座⼩岛上⽣活的家族有⼀个有趣的现象：同⼀个家族的⼈家总是相邻的这⾥的相邻是指东南⻄北四个⽅向，不同的家族之间总会有河流或是⼭丘隔绝，但同⼀个家族的⼈不⼀定有相同姓⽒。现在给你岛上的地图，求出岛上有多少个不同的家族。岛上的地图有⾏，每⾏有若⼲列，每个格⼦中要么是空格，表示⼤海，要么是“*”，表示河流或⼭丘，要么是⼩写字⺟，表示⼀户⼈家的姓⽒

输入

第⼀⾏⼀个整数数字，表示下⾯信息的⾏数。接下来是⾏字符，每⾏由⼩写字⺟和"*"号组成，有些⾏的最前⾯也可能包含若⼲连续的空格，表示这些区域是⼤海，每⼀⾏最多不超过个字符

输出

⼀个数字，表示家族数

对于10%的数据，保证n≤1 对于30%的数据，保证 n≤10 对于100%的数据，保证n≤100且每⼀⾏最多不超过200个字符

CPP

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
string a[105];
int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
void dfs(int x,int y) {
	a[x][y]='*';
	for(int i=0;i<4;i++){
		int nx=x+fx[i];
		int ny=y+fy[i];
		if(nx<1||ny<1||nx>n||ny>a[x].size()) continue;
		if(!islower(a[nx][ny])) continue; 
        dfs(nx,ny);
	}

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<=n;i++){
		getline(cin,a[i]);
	}
    for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i].size();j++){
			if(islower(a[i][j])){
				dfs(i,j);
				cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
}

10Pts求条

站外题求条

讨论操作

题目描述

输入

输出

回复

相关推荐

站外题求条