试题EE：七段码

【问题描述】

上图给出了七段码数码管的一个图示，数码管中一共有 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 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

---

 思路：将七段码分别标记为1，2，3，4，5，6，7并转化成图，dfs搜索将所有相连的点组合的所有方式记录下来，由于将组合的每个点大到小排序后一定是唯一的（比如1,2,3和2,3,1都只生成321这个数字），又因为将这些点生成的最大值只有7654321,所以我把这些组合都生成一个数字来表示，并通过set容器实现去重效果。

 需要输入图信息（在最下面的注释中）

#include<iostream>
#include<algorithm>
#include<vector>
#include<set> 
using namespace std;vector<int> g[10];
set<int> res;
bool vis[10];
int idx;//将tmp插入a，使得a的每一位都是大到小（有序形成唯一） 
int getNewNum(int a,int tmp){int b = 0;while(a && a%10 < tmp){b = b*10 + a%10;a /= 10;}a = a*10 + tmp;while(b){a = a*10 + b%10;b/=10;}return a;
}void dfs(int x,int num){for(int tmp:g[x]){if(!vis[tmp]){int a = getNewNum(num,tmp);res.insert(a);vis[tmp] = true;dfs(tmp,a);vis[tmp] = false;}}
} int main(){int m;cin>>m;for(int i = 1; i <= m; i++){int u,v;cin>>u>>v;//构建邻接表，也可以邻接矩阵 g[u].push_back(v);g[v].push_back(u);}for(int i = 1; i <= 7; i++){fill(vis,vis+10,0);//初始化 dfs(i,0);}printf("共有%d种\n",res.size());printf("****************以下为全部组合方式***********\n");for(int x:res){cout<<x<<'\n';}return 0;
} 
/*
10
1 2
1 3
2 4
3 4
2 5
3 6
4 5
4 6
5 7
6 7
*/