Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

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

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

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

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

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

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

例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。请问，小蓝可以用七段码数码管表达多少种不同的字符？

思路分析

看到“所有二极管需要连成一片”的要求，想到将二极管抽象为图。

怎么抽象？

虽然一眼看上去每个数码管长得挺像边的，但是根据题意，可以将数码管理解为顶点，相邻的数码管之间连无向边；这样的话，如果发光的数码管组成的无向图是连通图，则满足“连成一片”要求。

判断连通图的方法，我使用的是dfs广度搜索，选中一个点开始搜，搜完以后如果存在没有搜到的点，那么这个无向图就不是连通图，即不可以表示为字符。遍历所有可能的情况即可。

如何遍历所有可能的发光情况？每个发光管有发光和不发光两种情况，7位数码管，用7位二进制数即可表示，每一位1表示发光。建立数组
$node[8]$，每次遍历将发光的数码管代表的结点设为true。跑dfs的时候需要额外判断node是不是true，如果不是的话就不搜这个点。

代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
bool node[8];
vector<int> graph[8];
bool fd[8];

void dfs(int s){
	fd[s]=true;
	for(auto t:graph[s]){
		if(!fd[t]&&node[t]){
			dfs(t);
		}
	}
}
int is(){
	for(int i=1;i<=7;i++){
		if(node[i]){
			if(!fd[i])return 0;
		}
	}
	return 1;
}
void add(int a,int b){
	graph[a].push_back(b);
	graph[b].push_back(a);
}
int main(){
	int cnt=0;
	add(1,2);
	add(1,3);
	add(2,4);
	add(2,5);
	add(3,4);
	add(3,6);
	add(4,5);
	add(4,6);
	add(5,7);
	add(6,7);
	for(int i=0b0000001;i<=0b1111111;i++){
		memset(fd,0,sizeof(fd));
		memset(node,0,sizeof(node));
		for(int j=1;j<=7;j++){
			if((i>>(j-1))%2==1){
				node[j]=true;
			}
		}
		for(int j=1;j<=7;j++){
			if(node[j]){
				dfs(j);
				break;
			}
		}
		if(is())cnt++;
	}
	cout<<cnt;
}

答案

80

总结

简而言之，这道题考的还是对于实际应用的抽象能力，只要想到该用那种算法做，就可以用最基础的图论算法解决。

这是蓝桥杯第十一届c++A组的一道填空题，难度中等，写的时候花了一些时间。这是我今年备考蓝桥杯的刷的第一道比较难的题，手法略显生疏。相信之后的刷题可以越来越顺手。