jzoj家族【DFS】

家族【DFS】"/>

jzoj家族【DFS】

>Description
在一个与世隔绝的岛屿上，有一个有趣的现象：同一个家族的人家总是相邻的（这里的相邻是指东南西北四个方向），不同的家族之间总会有河流或是山丘隔绝，但同一个家族的人不一定有相同姓氏。现在给你岛上的地图，求出岛上有多少个不同的家族。岛上的地图有n 行，每行有若干列，每个格子中要么是’空格表示大海，要么是‘ *’，表示河流或山丘，要么是小写字母，表示一户人家的姓氏。

>Input
第一行是个数字 N，表示下面信息的行数，接下来是 N 行字符，每行由小写字母和*号组成，有些行的最前面也可能包含若干连续的空格，表示这些区域是大海，每一行最多不超过 200 个字符。

>Output
一个数字，表示家族数。

>Sample Input
4
zlw**pxh
lzlwkhx
w*tyy**yyy
zzl

>Sample Output
3

【数据范围】
10%的数据， n<=1
30%的数据， n<=10
100% 的数据， n<=100 每一行最多不超过 200 个字符

>解题思路

>代码

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int xx[4]={-1,0,0,1},yy[4]={0,-1,1,0};
int n,ans;
string s[105];
bool yd[105][205];
char cc;
void lil(int x,int y)
{yd[x][y]=1; //标记for(int i=0;i<4;i++)if(x+xx[i]>=1&&x+xx[i]<=n&&y+yy[i]>=0&&y+yy[i]<s[x+xx[i]].size()) //越界if(!yd[x+xx[i]][y+yy[i]]&&s[x+xx[i]][y+yy[i]]!='*'&&s[x+xx[i]][y+yy[i]]!=' ') //判断是不是属于同一家族lil(x+xx[i],y+yy[i]);
}
string input()
{string a="";char c=getchar();while((c>'z'||c<'a')&&c!='*'&&c!=' ') c=getchar();while((c<='z'&&c>='a')||c=='*'||c==' '){a+=c;c=getchar();}return a;
} //输入要这么麻烦才可以100（我太水）
int main()
{
//	freopen("family.in","r",stdin);
//	freopen("family.out","w",stdout);scanf("%d",&n);cc=getchar();for(int i=1;i<=n;i++)s[i]=input();for(int i=1;i<=n;i++)for(int j=0;j<s[i].size();j++)if(!yd[i][j]&&s[i][j]!='*'&&s[i][j]!=' '){lil(i,j);ans++;}printf("%d",ans);return 0;
}