试题 D: 七段码
本题总分：10 分
【问题描述】
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如： b 发光，其他二极管不发光可以用来表达一种字符。
例如： c 发光，其他二极管不发光可以用来表达一种字符。这种 方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如： a, b, c, d, e 发光， f, g 不发光可以用来表达一种字符。
例如： b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【思路】
深度优先搜索+状态压缩+HashSet唯一性
【Java代码】
package lanqiao2020; import java.util.ArrayList; import java.util.HashSet; public class test { //使用HashSet可以唯一性存储符合条件的数码管亮灭情况状态 static HashSet<Integer> set = new HashSet<>(); //使用邻接链表存储数码管连通情况 static ArrayList<Integer>[] list = new ArrayList[7]; public static void main(String[] args) { //初始化连通情况 for(int i = 0; i < 7; i++) { list[i] = new ArrayList<Integer>(); } list[0].add(1); list[0].add(5); list[1].add(0); list[1].add(6); list[1].add(2); list[2].add(1); list[2].add(3); list[2].add(6); list[3].add(2); list[3].add(4); list[4].add(3); list[4].add(5); list[4].add(6); list[5].add(0); list[5].add(4); list[5].add(6); list[6].add(1); list[6].add(2); list[6].add(4); list[6].add(5); //以每个数码管作为起点（即在该数码管必须亮情况下） for (int i = 0; i < 7; i++) { set.add(1<<i); //单独亮也符合情况，所以存储进去 dfs(1, i, 1<<i); //深度优先搜索 } System.out.println(set.size()); //因为唯一性，所以set中元素的个数即为符合条件的数码管亮灭状态的数量 } //深度优先搜索，第一个参数代表当前亮了几个数码管，第二个参数代表当前最近亮起的数码管，第三个参数即为当前状态（如0000001代表0号数码管亮，其余不亮） static void dfs(int total, int cur, int state) { //最多亮起7个数码管 if (total == 7) { return; } for (Integer item : list[cur]) { if (!set.contains(state | (1<<item))) { set.add(state | (1<<item)); } dfs(total+1, item, state | (1<<item)); } } }
