题目描述
小兰用七段码数码管来表示一种特殊的文字。
上图显示了七段码数码管的图表，共有数码管 77 段能发光的二 极管，分别标记为 a, b, c, d, e, f, ga,b,c,d,e,f,g。
小蓝要选择一部分二极管(至少一个)发光来表达字符。设计字符 所有发光的二极管都需要连接在一起。
例如：bb 发光，其他二极管不发光可以用来表达一个字符。
例如 cc 发光，其他二极管不发光可以用来表达一个字符。该方案与上述方案相匹配 尽管看起来相似，但一行方案可以用来表示不同的字符。
例如：a, b, c, d, ea,b,c,d,e 发光，f, gf,g 不发光可以用来表达一个字符。
例如：b, fb,f 发光，其他二极管不发光，因为发光 二极管没有连成一片。
小蓝能用七段码数码管表达多少种不同的字符？
运行限制
- 最大运行时间：1s
- 最大运行内存： 128M
这个问题，我看到的时候，首先是手算的。一开始数了60多，后来数了76，还是错的。我是个残忍的人...但毕竟是道填空题，手算时间可能划算。
然后我想用图片来做，但我一直想不出一个想法。我在这里看到了一个大人物的代码。具体想法是dfs和收集，豁然开朗！
链接如下：
[蓝桥杯2020] E题.七段码 //dfs 并查集_晚樱-CSDN博客_蓝桥杯七段码
代码如下：
#include <bits/stdc .h> using namespace std; const int N=10; int use[N],ans,e[N][N],fa[N]; void init() { e[1][2]=e[1][6]=1; e[2][1]=e[2][3]=e[2][7]=1; e[3][2]=e[3][4]=e[3][7]=1; e[4][3]=e[4][5]=1; e[5][4]=e[5][6]=e[5][7]=1; e[6][1]=e[6][5]=e[6][7]=1; e[7][2]=e[7][3]=e[7][5]=e[7][6]=1; } int find(int u) { if(fa[u]==u) return u; fa[u]=find(fa[u]); return fa[u]; } void dfs(int d) { if(d>7) { for(int i=1;i<=7; i) fa[i]=i; for(int i=1;i<=7; i) { for(int j=1;j<=7; j) { //两盏相邻的灯直接合并 if(e[i][j]&&use[i]&&use[j]) { int fa1=find(i),fa2=find(j); if(fa1!=fa2) fa[fa2]=fa1; } } } int k=0; for(int i=1;i<=7; i) { if(fa[i]==i&&use[i]) { k ; } } if(k==1) ans ; return; } use[d]=1; dfs(d 1); use[d]=0; dfs(d 1); } int main() { // 请在此输入您的代码 // cout<<7 10 14 20 17 7 1; init(); dfs(1); cout<<ans; return 0; }我对这个代码的理解是，dfs它被用来开关一个侧面的，像一个排列组合一样经历所有情况，并收集和组合use[]（use[i]=1说明第一盏灯亮，0则不亮)数组判断是否含有连续亮灯的集合，真的很棒~