七段码

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

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

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

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

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

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

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

例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

运行限制

最大运行时间：1s
最大运行内存: 128M

分析

纯纯回溯算法。 visit数组代表是否点亮。思路是一段的数量=该段自己亮+该段亮且连通分支的数量。 最后由于每种情况都被算了两遍，故而要除以2 【注：关于为什么被算了两遍： 比如说单纯看c亮a亮情况。在计算a亮时算了一遍，在计算c亮时又算了一遍 】

提交答案

#include <iostream>
using namespace std;

int BackTrack(int graph[][7],int visit[],int n,int i){
  int count=1;
  for(int x=0;x<n;x++){
    if(visit[x]!=1&&graph[i][x]!=0){
      visit[x]=1;
      count+=BackTrack(graph,visit,n,x);
      visit[x]=0;
    }
  }
  return count;
}
int main()
{
  int graph[7][7]={
    {1,1,0,0,0,1,0},
    {1,1,1,0,0,0,1},
    {0,1,1,1,0,0,1},
    {0,0,1,1,1,0,0},
    {0,0,0,1,1,1,1},
    {1,0,0,0,1,1,1},
    {0,1,1,0,1,1,1}
  };
  int visit[7]={0};
  printf("%d",BackTrack(graph,visit,7,0)/2);
  return 0;
}