十一届蓝桥杯省赛B组试题E：七段码

// 七段码.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//思想：二进制求子集，深度优先遍历
#include <iostream>
#include<math.h>
using namespace std;
int b[7];
int map[7][7];
void judge()
{
	int i, j, k;
	
	for (i = 0; i < 7; i++)//初始化
		for (j = 0; j < 7; j++)
			map[i][j] = 0;
	map[0][1] = 1;//建立关系图
	map[0][5] = 1;

	map[1][2] = 1;
	map[1][0] = 1;
	map[1][6] = 1;

	map[2][1] = 1;
	map[2][6] = 1;
	map[2][3] = 1;

	map[3][2] = 1;
	map[3][4] = 1;

	map[4][3] = 1;
	map[4][6] = 1;
	map[4][5] = 1;

	map[5][6] = 1;
	map[5][4] = 1;
	map[5][0] = 1;

	map[6][1] = 1;
	map[6][2] = 1;
	map[6][4] = 1;
	map[6][5] = 1;



}
void gg(int k)//用于判断是否连在一起，从第k个字母开始搜索所有能与与第k个字母连在一起的字母并标记为2
{
	int i,j;
	b[k] = 2;
	for (i = 0; i < 7; i++)
	{
		if (map[k][i]==1 && b[i] == 1)//深度优先遍历
			gg(i);
	}
	

}
int main()
{
	int i,j,k,l,n,m,g,sum=0;
	judge();
	for (i = 1; i < (1 << 7); i++)//用于生成7个字母的所有子集,注意i为0的时候是空集要去掉
	{
		for (l = 0; l < 7; l++)//初始化
			b[l] = 0;
		k = 0;//用于记录在数组b中放了多少个字母
		for (j = 0; j < 7; j++)//生成子串
			if (i & (1 << j))
			{
				b[j] = 1;//1表示在j位置上是字母在子串里
				k++;
			}
		for (g = 0; g < 7; g++)//找到第一个字母所在位置
		{
			if (b[g] == 1)
			break;
		}
		gg(g);
		m = 0;
		for (n = 0; n < 7; n++)//当与第g个字母连在一起的字母个数和等于k个时说明k个字母都连在了一起
			if (b[n] == 2)
				m++;
		if(m==k)
			sum++;
		
	}
	cout<<sum;
	
	

}