【DFS】七段码【蓝桥杯】

题目

七段码 - 蓝桥云课

---

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

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

上图给出了七段码数码管的一个图示，数码管中一共有 $7$ 段可以发光的二 极管，分别标记为 $a, b, c, d, e, f, g$。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

例如：$b$ 发光，其他二极管不发光可以用来表达一种字符。

例如 $c$ 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：$a, b, c, d, e$ 发光，$f, g$ 不发光可以用来表达一种字符。

例如：$b, f$ 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

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

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

解题

方法一：DFS

思路

附加了特殊限制的指数型枚举，由于最多只有 $7$ 种字母选择，直接DFS暴搜即可。

代码

import java.util.*;
import java.io.*;

public class Main {
    static Map<Character, char[]> mp = new HashMap<>();
    static Set<Set<Character>> st = new HashSet<>();
    static {
        mp.put('a', new char[]{'f', 'b'});
        mp.put('b', new char[]{'a', 'g', 'c'});
        mp.put('c', new char[]{'d', 'g', 'b'});
        mp.put('d', new char[]{'c', 'e'});
        mp.put('e', new char[]{'d', 'g', 'f'});
        mp.put('f', new char[]{'a', 'g', 'e'});
        mp.put('g', new char[]{'f', 'e', 'c', 'b'});
    }

    static void dfs(Set<Character> curr, char c) {
        st.add(curr);
        if (curr.size() == 7) return;
        for (char ch : mp.get(c)) {
            if (curr.contains(ch)) continue;
            Set<Character> newSet = new HashSet<>(curr);
            newSet.add(ch);
            dfs(newSet, ch);
        }
    }

    public static void main(String[] args) {
        for (char c = 'a'; c <= 'g'; ++c) {
            Set<Character> curr = new HashSet<>();
            curr.add(c);
            dfs(curr, c);
        }
        System.out.println(st.size());
    }
}