Topic Description

There are 9 lights and 9 switches, numbered 1-9.  

Each switch can control a number of lights, and the next press will change the state of the lights it controls (turn on or off to turn on).  

Specifically as follows:

The first switch controls the second and fourth lights.

The second switch controls the first, third and fifth lights.

The third switch controls the second and sixth lights.

The fourth switch controls the first, fifth and seventh lights.

The fifth switch controls the second, fourth, sixth and eighth lights.

The sixth switch controls the third, fifth and ninth lights.

The seventh switch controls the fourth and eighth lights.

The eighth switch controls the fifth, seventh and ninth lamps.

The ninth switch controls the sixth and eighth lights.  

At first all the lights went out and the switch was off. After several switches were pressed, only four lights were on.  

input

nothing

output

Output all possible scenarios, one scenario per line, each line has 9 characters, from left to right, the first character represents the state of the second switch ("0" means close, and "1" means open), output in dictionary order. The following sample output is only part of the solution.  

sample input

nothing

sample output

000001011 
000001110 
000001111 

#include<iostream>
#include<set>
#include<vector>
using namespace std;
vector<int> op[10];
set<vector<int> > ans;
vector<int> show(10,0),state(10,0);
bool judge(vector<int> & show){
	int cnt = 0;
	for(int i = 1;i <= 9;i ++){
		if(show[i] == 1) cnt ++; 
	}
	return cnt == 4;
}

void dfs(int idx,bool press){
	if(idx == 10){
		if(judge(show)){
			ans.insert(state);
		}
		return;
	}
	if(press){
		state[idx] = 1;
		for(int i = 0;i < op[idx].size();i ++){
			show[op[idx][i]] ^= 1;
		}
		dfs(idx+1,1);
		dfs(idx+1,0);
		state[idx] = 0;
		for(int i = 0;i < op[idx].size();i ++){
			show[op[idx][i]] ^= 1;
		}
	}
	else{
		dfs(idx+1,1);
		dfs(idx+1,0);
	}
}
int main()
{
	op[1].push_back(2);
	op[1].push_back(4);
	
	op[2].push_back(1);
	op[2].push_back(3);
	op[2].push_back(5);
	
	op[3].push_back(2);
	op[3].push_back(6);
	
	op[4].push_back(1);
	op[4].push_back(5);
	op[4].push_back(7);
	
	op[5].push_back(2);
	op[5].push_back(4);
	op[5].push_back(6);
	op[5].push_back(8);
	
	op[6].push_back(3);
	op[6].push_back(5);
	op[6].push_back(9);
	
	op[7].push_back(4);
	op[7].push_back(8);
		
	op[8].push_back(5);
	op[8].push_back(7);
	op[8].push_back(9);
	
	op[9].push_back(6);
	op[9].push_back(8);
	
	dfs(0,0);
	for(set<vector<int> >::iterator it = ans.begin();it != ans.end();it ++){
		vector<int> tmp = *it;
		for(int i = 1;i <= 9;i ++){
			cout<<tmp[i];
		}
		cout<<endl;
	}
	return 0;
}