侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】七段码【蓝桥杯】

GabrielxD
2022-12-26 / 0 评论 / 0 点赞 / 15 阅读 / 662 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

七段码 - 蓝桥云课


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

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

img

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

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

运行限制

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

解题

方法一:DFS

思路

附加了特殊限制的指数型枚举,由于最多只有 77 种字母选择,直接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());
    }
}
0

评论区