七段码（枚举 or dfs + 并查集）

本题为2020年蓝桥杯C/C++省赛B组第二场 E:七段码

本题我将使用C++来解题。

先说本题答案：80

在本题中，将 a 视为 1，b 视为 2 … c 视为 7

1、枚举 + 并查集

思路：依次枚举每个二极管的亮、灭情况，再通过并查集确定它们是否连通，统计所有符合条件的情况。

由于共有7个二极管，则总共有 2^7 种情况。

#include
using namespace std;

const int N=10;
bool mp[N][N];	// 二极管之间的连通情况 
bool tmp[N];	// 某个二极管是否亮 
int father[N];	// 某个二极管的父节点 
int ans;	// 答案，全局变量默认为 0 

void set_mp()	// 初始化mp，mp[1][2]=true意味着1(a)与2(b)连通 
{
	mp[1][2]=mp[1][6]=true;
	mp[2][1]=mp[2][3]=mp[2][7]=true;
	mp[3][2]=mp[3][4]=mp[3][7]=true;
	mp[4][3]=mp[4][5]=true;
	mp[5][4]=mp[5][6]=mp[5][7]=true;
	mp[6][1]=mp[6][5]=mp[6][7]=true;
	mp[7][2]=mp[7][3]=mp[7][5]=mp[7][6]=true;
}

int findf(int i)	// 找 i 的父节点 
{
	if(father[i]==i)return i;
	return findf(father[i]);
}

int main()
{
	set_mp();	// 初始化 
	
	for(int x=1;x<(1<<7);x++)	// 枚举所有的情况 
	{
		memset(tmp,0,sizeof(tmp));	// 清空亮灭情况 
		int temp=x,id=1;
		
		while(temp)	// 通过temp计算某个二极管是否亮、灭 
		{
			if(temp%2)
			{
				tmp[id]=true;
				father[id]=id;
			}
			temp>>=1;
			id++;
		}
		
		for(int i=1;i<=7;i++)	// 划分连通区域 
		{
			for(int j=i+1;j<=7;j++)
			{
				if(tmp[i]==0||tmp[j]==0)continue;
				
				if(mp[i][j])father[findf(i)]=findf(j);
			}
		}
		
		int sum=0;
		for(int i=1;i<=7;i++)	// 求连通区域总和 
		{
			if(tmp[i]&&father[i]==i)sum++;
		}
		
		if(sum==1)ans++;	// 连通区域只有一个的才符合条件 
	}
	
	cout<<ans;
	
	return 0;
}

2、dfs + 并查集

思路：通过递归算出每个二极管的亮、灭情况，再通过并查集确定它们是否连通，统计所有符合条件的情况，总体跟枚举差不多。

#include
using namespace std;

const int N=10;
bool mp[N][N];	// 二极管之间的连通情况 
bool tmp[N];	// 某个二极管是否亮 
int father[N];	// 某个二极管的父节点 
int ans;	// 答案，全局变量默认为 0 

void set_mp()	// 初始化mp，mp[1][2]=true意味着1(a)与2(b)连通 
{
	mp[1][2]=mp[1][6]=true;
	mp[2][1]=mp[2][3]=mp[2][7]=true;
	mp[3][2]=mp[3][4]=mp[3][7]=true;
	mp[4][3]=mp[4][5]=true;
	mp[5][4]=mp[5][6]=mp[5][7]=true;
	mp[6][1]=mp[6][5]=mp[6][7]=true;
	mp[7][2]=mp[7][3]=mp[7][5]=mp[7][6]=true;
}

int findf(int i)	// 找 i 的父节点 
{
	if(father[i]==i)return i;
	return findf(father[i]);
}

void f(int n)
{
	if(n>7)	// 已算出7个灯的亮灭情况 
	{
		for(int i=1;i<=7;i++)
		{
			if(tmp[i])father[i]=i;
		}
		
		for(int i=1;i<=7;i++)	// 划分连通区域 
		{
			for(int j=i+1;j<=7;j++)
			{
				if(tmp[i]==0||tmp[j]==0)continue;
				
				if(mp[i][j])father[findf(i)]=findf(j);
			}
		}
		
		int sum=0;
		for(int i=1;i<=7;i++)	// 求连通区域总和 
		{
			if(tmp[i]&&father[i]==i)sum++;
		}
		
		if(sum==1)ans++;	// 连通区域只有一个的才符合条件 
		
		return;
	}
	
	tmp[n]=0;	// 当前灯为灭 
	f(n+1);		// 考虑下一个灯的情况 
	
	tmp[n]=1;	//当前灯为亮 
	f(n+1);		// 考虑下一个灯的情况
}

int main()
{
	set_mp();	// 初始化 
	f(1);		// 从第 1 个灯开始 
	
	cout<<ans;
	
	return 0;
}