题目描述：
算法提高 开灯游戏
时间限制：1.0s 内存限制：256.0MB
问题描述
有9盏灯与9个开关，编号都是1~9。
每个开关能控制若干盏灯，按下一次会改变其控制的灯的状态(亮的变成不亮，不亮变成亮的)。
具体如下：
第一个开关控制第二，第四盏灯；
第二个开关控制第一，第三，第五盏灯；
第三个开关控制第二，第六盏灯；
第四个开关控制第一，第五，第七盏灯；
第五个开关控制第二，第四，第六，第八盏灯；
第六个开关控制第三，第五，第九盏灯；
第七个开关控制第四，第八盏灯；
第八个开关控制第五，第七，第九盏灯；
第九个开关控制第六，第八盏灯。
开始时所有灯都是熄灭的，开关是关闭着的。要求按下若干开关后，使得只有4盏灯亮着。
输出格式
输出所有可能的方案，每行一个方案，每一行有9个字符，从左往右第i个字符表示第i个开关的状态(" 0" 表示关闭，" 1" 表示打开)，按字典序输出。下面的样例输出只是部分方案。
样例输出
000001011
000001110
000001111
程序代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int k[10];//开关的状态 int d[10];//灯的状态 void change(int &i)//引用，改变灯的状态 {//此处的 &i 相当于 d[] if(i==0) i=1; else if(i==1) i=0; } void judge() { for(int i=1;i<=9;i++) { if(k[i]==1) { if(i==1) { change(d[2]); change(d[4]); } else if(i==2) { change(d[1]); change(d[3]); change(d[5]); } else if(i==3) { change(d[2]); change(d[6]); } else if(i==4) { change(d[1]); change(d[5]); change(d[7]); } else if(i==5) { change(d[2]); change(d[4]); change(d[6]); change(d[8]); } else if(i==6) { change(d[3]); change(d[5]); change(d[9]); } else if(i==7) { change(d[4]); change(d[8]); } else if(i==8) { change(d[5]); change(d[7]); change(d[9]); } else if(i==9) { change(d[6]); change(d[8]); } } } int sum=0,flag=0; for(int i=1;i<=9;i++) { if(d[i])//有一盏灯是亮的 sum++;//计数加1 } if(sum==4)//满足题意的四盏灯是亮的 { flag=1; for(int i=1;i<=9;i++) cout<<k[i];//输出对应的开关的状态 } if(flag) cout<<endl; } void dfs(int s) { if(s==10) { judge(); memset(d,0,sizeof(d)); return ; } for(int i=0;i<2;i++) { k[s]=i; dfs(s+1); } } int main() { memset(k,0,sizeof(k)); memset(d,0,sizeof(d)); dfs(1); return 0; }
