小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示,数码管中一共有 7 段可以发光的二极管,分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管(至少要有一个)发光来表达字符。
在设计字符的表达时,要求所有发光的二极管是连成一片的。
例如:b 发光,其他二极管不发光可以用来表达一种字符。
例如:c 发光,其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符,尽管看上去比较相似。
例如:a, b, c, d, e 发光,f, g 不发光可以用来表达一种字符。
例如:b, f 发光,其他二极管不发光则不能用来表达一种字符,因为发光的二极管没有连成一片。
请问,小蓝可以用七段码数码管表达多少种不同的字符?
答案:80
#include<bits/stdc++.h>
using namespace std;
int use[10];
int ans,e[10][10],father[10];
void init()
{
//连边建图
//a b c d e f g
//1 2 3 4 5 6 7
e[1][2]=e[1][6]=1;
e[2][1]=e[2][7]=e[2][3]=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;
}
int find(int a)//并查集
{
return (a==father[a])? a:father[a]=find(father[a]);
}
void dfs(int d)
{
if(d>7)
{
for(int i=1;i<=7;i++)
{
father[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 fa=find(i),fb=find(j);
if(fa!=fb)
{
father[fa]=fb;
}
}
}
}
int k=0;
for(int i=1;i<=7;i++){
if(use[i]&&i==father[i])k++;
}
if(k==1)ans++;//只有一个连通块就统计
return;
}
use[d]=0;//不选
dfs(d+1);
use[d]=1;//选
dfs(d+1);
use[d]=0;
}
int main()
{
init();
dfs(1);
cout<<ans;
return 0;
}