题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝要用七段码数码管来表示一种特殊的文字。

图片描述

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

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

dfs+并查集

方法

思路

dfs搜索所有状态，判断每种状态可不可行。
判断的方法是把每条灯管当作一个节点，编号，连边建图，对搜索出的亮灯方案使用并查集判断点亮的灯管是否在同一个集合。

进行递归，先将1-7都点亮，有一种字符；再一步一步返回上一级，先是7灭，有一种字符；然后6灭，6灭的时候里面又分为7灭或者不灭，有几种字符；接着5灭，5灭的时候里面又分为6灭/不灭，7灭/不灭几种可能，有几种字符.

C++ 代码

#include<iostream>

using namespace std;

int st[8];//1为亮0为不亮
int g[8][8];//邻接矩阵存储图
int f[8];//并查集
int res;

int find(int x){
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void dfs(int u){
    if(u>7){

        for(int i=1;i<=7;i++) f[i]=i;//初始化集合

        for(int i=1;i<=7;i++)
            for(int j=1;j<=8;j++){
                if(g[i][j]&&st[i]&&st[j])//如果i和j联通而且i和j是同时亮着的,则将i和j并为一个集合
                {
                    int a=find(i),b=find(j);
                    if(a!=b) f[a]=b;
                }
            }

        int t=0;//计算点亮的所有中共有多少个连通块
        for(int i=1;i<=7;i++)
            if(f[i]==i&&st[i]) t++;

        if(t==1) res++;//如果仅有一个连通，则说明符合题意，可行

        return;//终止函数

    }
    st[u]=1;
    dfs(u+1);
    st[u]=0;
    dfs(u+1);
}

/*
a b c d e f g 
1 2 3 4 5 6 7
*/
int main(){
    g[1][2]=g[1][6]=1;
    g[2][1]=g[2][7]=g[2][3]=1;
    g[3][2]=g[3][7]=g[3][4]=1;
    g[4][3]=g[4][5]=1;
    g[5][4]=g[5][7]=g[5][6]=1;
    g[6][5]=g[6][1]=g[6][7]=1;
    g[7][2]=g[7][3]=g[7][5]=g[7][6]=1;

    dfs(1);

    cout<<res<<endl;

    return 0;

}