Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

Blue had to use seven code nixie tubes to represent a particular kind of text.

The figure above shows a diagram of a seven-bit digital tube with seven light-emitting diodes, labeled A, B, C, D, E, F, and G.

Blue selects a portion of the diode (at least one) to emit light to express the character. When designing the expression of characters, it is required that all leds are connected together.

For example: B light, other diodes do not light can be used to express a character.

For example: C light, other diodes do not light can be used to express a character. This scheme can be used to represent different characters from the previous one, although it looks similar.

For example: A, B, C, D, e light, f, g not light can be used to express a character.

For example: B, F light, other diodes do not light can not be used to express a character, because the light-emitting diodes are not connected. How many different characters can blue express with seven code nixie tube?

Thought analysis

Seeing the requirement that “all diodes need to be connected together”, it occurred to me to abstract the diode as a graph.

How abstract?

Although at first glance each digital tube looks like an edge, digital management can be resolved as a vertex, with undirected edges between adjacent digital tubes. Thus, if the undirected graph of the illuminated nibbles is a connected graph, it meets the “contiguous” requirement.

To judge the connected graph, I use DFS breadth search to select a point and start the search. After the search, if there is any point not found, the undirected graph is not a connected graph, that is, it cannot be expressed as a character. Just go through all the possible scenarios.

How do I traverse all possible luminous conditions? Each light tube has light and not light two situations, 7 bit digital tube, with 7 bits of binary number can be represented, each 1 represents light. Create an array node[8]node[8] and set the node represented by the illuminated nixtube to true for each traversal. When running DFS, you need to check whether node is true. If not, skip the search.

code

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
bool node[8];
vector<int> graph[8];
bool fd[8];

void dfs(int s){
	fd[s]=true;
	for(auto t:graph[s]){
		if(! fd[t]&&node[t]){dfs(t); }}}int is(a){
	for(int i=1; i<=7; i++){if(node[i]){
			if(! fd[i])return 0; }}return 1;
}
void add(int a,int b){
	graph[a].push_back(b);
	graph[b].push_back(a);
}
int main(a){
	int cnt=0;
	add(1.2);
	add(1.3);
	add(2.4);
	add(2.5);
	add(3.4);
	add(3.6);
	add(4.5);
	add(4.6);
	add(5.7);
	add(6.7);
	for(int i=0b0000001; i<=0b1111111; i++){memset(fd,0.sizeof(fd));
		memset(node,0.sizeof(node));
		for(int j=1; j<=7; j++){if((i>>(j- 1)) %2= =1){
				node[j]=true; }}for(int j=1; j<=7; j++){if(node[j]){
				dfs(j);
				break; }}if(is())cnt++;
	}
	cout<<cnt;
}
Copy the code

The answer

80

conclusion

In short, this problem is still for the practical application of abstraction, as long as you think of which algorithm to do, you can use the most basic graph algorithm to solve.

Blue bridge cup 11th c++ group A A fillin problem, medium difficulty, writing time took some time. This is my preparation this year blue bridge cup brush the first more difficult problem, the technique slightly rusty. I believe that the brush problem can be more and more smoothly.