七段码（2020年蓝桥杯省赛）

题目

小蓝要用七段码数码管来表示一种特殊的文字。 上图给出了七段码数码管的一个图示，数码管中一共有7 段可以发光的二极管，分别标记为a, b, c, d, e, f, g。 小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。 例如：b 发光，其他二极管不发光可以用来表达一种字符。 例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。 请问，小蓝可以用七段码数码管表达多少种不同的字符？

思路

我的思路参考自这个博客： dfs+并查集。 dfs的思想就是，对于每一根发光二极管，都可以选或者不选，从而枚举发光二极管的所有选择情况，然后在递归结束的地方用并查集的思路去判断我选择的这些发光二极管是不是连成一片（在同一个集合中）。如果确实连成一片，就计数1次。 枚举就枚举，结果填空题也不怕超时。哈哈 并查集在《算法笔记》上是有一套模板的，非常通俗易懂。对于这个题，只是多加入了一个bool型数组used[]，来标记某一根二极管是不是被选中了。 答案是80

代码

#include<cstdio>
using namespace std;
bool used[10];
int e[10][10];
int father[10];
int ans=0;
void init()
{
	for(int i=0; i<10; i++) {
		for(int j=0; j<10; j++) {
			e[i][j] = 0;
		}
	}
	// a b c d e f g
	// 1 2 3 4 5 6 7
	// 用二维数组来记录哪两条边是相连的
	e[1][2]=e[1][6]=1;
	e[2][7]=e[2][3]=1;
	e[3][4]=e[3][7]=1;
	e[4][5]=1;
	e[6][7]=1;
	e[5][6]=e[5][7]=1;
}
int findFather(int x) {
	int a=x;
	while(x != father[x]) {
		x = father[x];
	}
	while(a != father[a]) {
		int z=a;
		a = father[a];
		father[z] = x;
	}
	return x;
}
void Union(int a, int b) {
	int faA = findFather(a);
	int faB = findFather(b);
	if(faA != faB) {
		father[faA] = faB;
	} 
}
void dfs(int index) { // index指的是已经判断完第index根二极管
	if(index==7) { // 如果已经到达递归末尾
		// 初始化 
		for(int i=1; i<=7; i++) {
			father[i]=i;
		}
		// 二重循环遍历：合并 
		for(int i=1; i<=7; i++) {
			for(int j=i+1; j<=7; j++) {
				if(e[i][j]==1 && used[i]==true && used[j]==true) {
					Union(i, j); 
				}
			}
		} 
		// 判断是不是在一个集合中 
		int cnt=0;
		for(int i=1; i<=7; i++) {
			if(used[i]==true && father[i]==i) cnt++;
		}
		if(cnt==1) ans++;
		return;
	}
	used[index+1] = true; // 选择某一根二极管就把它的used[]置为1
	dfs(index+1); // 分支1 
	used[index+1] = false;
	dfs(index+1); // 分支2 
}
int main()
{
	init();
	dfs(0); 
	printf("%d
",ans);
	return 0;
}

注意

开始给数组e[][]赋值时，是数字小的下标在前面，数字大的下标在后面。因此，在dfs()函数中，用二重循环遍历所有的2根二极管，对应的也是j比i大，j初始化为i+1。 findFather()和Union()都是算法笔记里的模板。