时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
从红魔馆的大门往里面看就可以看到一个大花园。园内不止种花，而且还种植了各种魔法药材供帕秋莉使用。芙兰对花园里的药材感到好奇，于是她就问红魔馆的门番兼园丁花园里有多少种不同的药材。但是红师傅在看门的时候不是在睡觉就是在睡觉！她只知道各种药材被分割开来，互不相邻。现在你从帕琪那里拿到了花园的地图，药材用小写字母表示，其他花草用’*'表示，空地用空格表示，你能替那个门番回答二小姐的问题吗？
顺便一提，同种药材也有优劣之分，帕琪可能会用不同的小写字母表示同一种药材，不同种类的药材一定是被其他花草或是空地分割开的。
输入
输入一个正整数n表示地图有n行
接着n行每行有一个字符串,包含小写字母,空格和’*'三种字符,意义如题面。
注意：每行都有可能以若干空格开头，且每行长度也不一定相同!
输出
一个正整数，表示药材的种类数。
样例输入 Copy
5 abca bbb* * * * abc e ccc
样例输出 Copy
3
提示
于10%的数据:n≤10,字符串长度≤10;
对于30%的数据: n≤100,字符串长度≤200;
对于100%的数据: n≤1000,字符串长度≤400;
题意
地图有三种符号，问由小写字母构成的连通块个数；
思路
dfs或并查集都可以写。
但是并查集比较麻烦，一般二维的并查集都可以用i*n+j转化为一维，但是这个题每一个字符串的长度是不确定的，所以这种转化方法并不适用。
如果想用并查集的话，可以用一个map+pair存一下这个位置对应的节点编号，用结构体存其他信息即可。
类似的题：传送门
代码
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; string s[maxn]; int vis[2100][2100]; int n; int nx[4]={0,0,1,-1}; int ny[4]={1,-1,0,0}; bool check(int x,int y){ if(x>=1&&x<=n&&y>=0&&y<s[x].size()&&(s[x][y]>='a'&&s[x][y]<='z')) return true; return false; } void dfs(int x,int y,int u){ vis[x][y]=u; for(int i=0;i<4;i++){ int xx=x+nx[i],yy=y+ny[i]; if(!vis[xx][yy]&&check(xx,yy)) dfs(xx,yy,u); } } void AC(){ scanf("%d",&n); for(int i=0;i<=n;i++){ getline(cin,s[i]); } ///for(int i=1;i<=n;i++) /// cout<<s[i]<<endl; memset(vis,0,sizeof vis); int res=0; for(int i=1;i<=n;i++) for(int j=0;j<s[i].size();j++) if(!vis[i][j]&&(s[i][j]>='a'&&s[i][j]<='z')){ res++; dfs(i,j,res); } cout<<res<<endl; } int main(){ AC(); return 0; }
![[Nowcoder] network | Tarjan 边双连通分量 | 缩点 | LCA倍增优化 | 并查集](https://ucc.alicdn.com/pic/developer-ecology/5554eff79239411c8300cad4838b1fe7.png?x-oss-process=image/resize,h_160,m_lfit)
