文章目录
- 七段码
- 题目描述
- 答案：80
- 分析
- 编程求解：有多种方法
- 方法一：状态压缩+枚举+构图（以二极管为顶点）+DFS判断连通
- 代码
- 方法二：bfs
七段码
题目描述
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
答案：80
分析
手工求解：容易遗漏，本题不宜采用。
编程求解：有多种方法
方法一：状态压缩+枚举+构图（以二极管为顶点）+DFS判断连通
- 状态压缩：一共才7段二极管，每段二极管都可以选或不选（全部不选不行），所以总共有27-1=127种方案，把1~127范围内的每个数转换成二进制，就对应到一种方案。
例如，（23）10=（0010111）2，表示a，b，c，e选，其他二极管不选。 - 枚举每个方案，看是否符合要求。
- 构图：以二极管为顶点，二极管相邻则连边。
- DFS判断连通：对每一种方案，从该方案中任何一个选中的顶点出发进行DFS，跳过那些没有选中的顶点，DFS完毕，如果所有选中的顶点都遍历到，则说明是连通的，是一种符合题目要求的方案。
方法重点：DFS、构图。
特征：方案，计数
核心思路：枚举所有方案，对预设的方案，通过关联等条件搜索DFS能覆盖此方案中所有亮的二极管，那么此方案计入方案数。
代码
这段代码的目的是计算可以用七段数码管表示的、所有发光的二极管连成一片的不同字符的数量。下面是对代码的详细注释：
#include<bits/stdc++.h>
using namespace std;
// 定义七段数码管中各个段之间的连接关系
int g[7][7] = {
0,1,0,0,0,1,0, // a段
1,0,1,0,0,0,1, // b段
0,1,0,1,0,0,1, // c段
0,0,1,0,1,0,0, // d段
0,0,0,1,0,1,1, // e段
1,0,0,0,1,0,1, // f段
0,1,1,0,1,1,0 // g段
};
// d数组用于标记当前方案中哪些段是亮的
int d[7];
// v数组用于标记在深度优先搜索中已经访问过的段
int v[7];
// 深度优先搜索函数，用于搜索所有与start相连的亮段
void dfs(int start) {
for(int i = 0; i < 7; i++) {
// 如果当前段i与start相连，且i段是亮的，且之前没有访问过i段
if(g[start][i] == 1 && d[i] == 1 && v[i] == 0) {
v[i] = 1; // 标记i段为已访问
dfs(i); // 递归调用dfs，继续搜索从i段出发的相连亮段
}
}
}
int main() {
int ans = 127; // 初始化答案为所有可能的组合数，即2^7 - 1（减1是因为至少有一个段是亮的）
for(int i = 1; i <= 127; i++) { // 遍历所有可能的组合
memset(d, 0, sizeof(d)); // 重置d数组为全0，表示所有段初始都是灭的
memset(v, 0, sizeof(v)); // 重置v数组为全0，表示没有段被访问过
int x = i, j = 0; // x为当前二进制数，j为当前位的索引
// 将i的二进制表示分解为一个个位，并存储到d数组中
while(x) {
d[j++] = x % 2; // 存储当前位的亮灭状态
x /= 2; // 移除已处理的位
}
// 找到第一个亮的段作为搜索的起点
int start = 0;
while(d[start] == 0) start++;
v[start] = 1; // 标记起点为已访问
dfs(start); // 从起点开始深度优先搜索
// 检查是否所有的亮段都已经被访问过
for(int j = 0; j < 7; j++) {
if(d[j] == 1 && v[j] == 0) {
ans--; // 如果有亮的段没有被访问过，说明当前方案不合法，答案减一
break; // 跳出循环，继续下一个组合
}
}
}
cout << ans; // 输出最终的合法组合数
return 0;
}
这段代码通过二进制的方式来表示每个字符的七段数码管的亮灭状态，然后通过深度优先搜索（DFS）来检查每个可能的组合是否满足题目中的条件（所有发光的二极管是连成一片的）。如果一个组合不满足条件，它会被排除，最终输出符合条件的字符数量。
方法二：bfs
这段代码的目的是使用广度优先搜索（BFS）来解决一个问题，具体来说，是计算在一个给定的图形（由七个点组成）中，有多少种方式可以使得所有点亮的点连成一片。这个问题可以通过检查每个点的连接性来解决。下面是对代码的详细注释：
#include<bits/stdc++.h>
using namespace std;
// ans用于记录连成一片的点亮点的数量
int ans;
// g[7][7]是一个二维数组，用于表示图形中点之间的连接关系
int g[7][7];
// vis[7]是一个数组，用于标记在BFS过程中已经访问过的点
int vis[7];
// flag[7]是一个数组，用于标记在检查过程中哪些点是亮的
int flag[7];
// BFS函数用于广度优先搜索，确定一个点是否连通其他亮的点
void bfs(int x){
queue<int> que; // 定义一个队列用于BFS
que.push(x); // 将起点x入队
vis[x] = true; // 标记x为已访问
while(!que.empty()){ // 当队列不为空时循环
int u = que.front(); // 取出队列前端的点
que.pop(); // 将该点从队列中移除
for(int i = 0 ; i <= 6 ; i ++){ // 遍历所有与u相连的点
if(g[u][i] && flag[i] && !vis[i]){ // 如果该点与u相连，且该点是亮的，且未被访问过
vis[i] = true; // 标记为已访问
que.push(i); // 将该点入队，继续BFS
}
}
}
}
// check函数用于检查一个给定的二进制编码x是否表示一个连通的图形
bool check(int x){
for(int i = 0 ; i <= 6 ; i ++) // 初始化flag和vis数组
flag[i] = vis[i] = false;
int cnt = 0; // 用于计数连通分量的数量
for(int i = 6 ; ~i ; i --) // 遍历x的每一位
if(x >> i & 1) flag[i] = true; // 如果某一位为1，则标记对应的点为亮的
for(int i = 0 ; i <= 6 ; i ++){ // 再次遍历每个点
if(flag[i] && !vis[i]){ // 如果点是亮的，但还未被访问
bfs(i); // 执行BFS
cnt ++ ; // 连通分量数量加一
}
}
return cnt == 1; // 如果只有一个连通分量，返回true
}
int main()
{
// 初始化g数组，表示图形中点之间的连接关系
g[0][1] = g[0][5] = 1;
g[1][0] = g[1][2] = g[1][6] = 1;
g[2][1] = g[2][3] = g[2][6] = 1;
g[3][2] = g[3][4] = 1;
g[4][3] = g[4][5] = g[4][6] = 1;
g[5][0] = g[5][4] = g[5][6] = 1;
g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
// 遍历所有可能的二进制编码（0到127）
for(int i = 0 ; i < (1 << 7) ; i ++){
if(check(i)) { // 如果当前编码表示一个连通的图形
ans ++ ; // 答案加一
}
}
cout << ans << '\n'; // 输出答案
return 0;
}
这段代码通过二进制编码来表示每个点的亮灭状态，然后使用BFS来检查每个点是否连通其他亮的点。check函数用于确定一个给定的编码是否表示一个连通的图形。如果是，那么答案ans就会增加。最后，程序输出所有可能的连通图形的数量。
