第十一届蓝桥杯C++B组 试题E：七段码

试题E：七段码

【问题描述】

上图显示了七段码数码管的图表，共有数码管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发光，其他二极管不发光，因为发光 二极管没有连成一片。

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

答案：80种

---

思路：将七段码分别标记为1、2、3、4、5、6、7，并转成图，dfs搜索记录所有连接点组合的所有方式，因为组合的每个点必须是唯一的（如1、2、3、2、3、3、1只生成321），因为这些点的最大值只有7654321，所以我生成一个数字来表示所有这些组合set去重效果的容器(也可以排序后去重)。

需要输入图信息(在下面的注释中)

#include #include #include #include  using namespace std;  vector g[10]; set res; bool vis[10]; int idx;  //将tmp插入a，让a的每一个人都大到小(只有有序形成)  int getNewNum(int a,int tmp){  int b = 0;  while(a && a < tmp){   b = b*10   a;   a /= 10;  }  a = a*10   tmp;  while(b){   a = a*10   b;   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<