2019-03-21 [蓝桥杯][算法提高VIP]开灯游戏

题目描述
有9盏灯与9个开关，编号都是1~9。

每个开关能控制若干盏灯，按下一次会改变其控制的灯的状态(亮的变成不亮，不亮变成亮的)。

具体如下：

第一个开关控制第二，第四盏灯；

第二个开关控制第一，第三，第五盏灯；

第三个开关控制第二，第六盏灯；

第四个开关控制第一，第五，第七盏灯；

第五个开关控制第二，第四，第六，第八盏灯；

第六个开关控制第三，第五，第九盏灯；

第七个开关控制第四，第八盏灯；

第八个开关控制第五，第七，第九盏灯；

第九个开关控制第六，第八盏灯。

开始时所有灯都是熄灭的，开关是关闭着的。要求按下若干开关后，使得只有4盏灯亮着。
输入
无
输出
输出所有可能的方案，每行一个方案，每一行有9个字符，从左往右第i个字符表示第i个开关的状态(" 0" 表示关闭，" 1" 表示打开)，按字典序输出。下面的样例输出只是部分方案。
样例输入
无
样例输出
000001011
000001110
000001111
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
int m[10],light[10];
int a[10][10];
vector<int>res;

int main(void)
{ 
    a[1][0]=2; a[1][1]=2,a[1][2]=4;
    a[2][0]=3; a[2][1]=1,a[2][2]=3,a[2][3]=5;
    a[3][0]=2; a[3][1]=2,a[3][2]=6;
    a[4][0]=3; a[4][1]=1,a[4][2]=5,a[4][3]=7;
    a[5][0]=4; a[5][1]=2,a[5][2]=4,a[5][3]=6,a[5][4]=8;
    a[6][0]=3; a[6][1]=3,a[6][2]=5,a[6][3]=9;
    a[7][0]=2; a[7][1]=4,a[7][2]=8;
    a[8][0]=3; a[8][1]=5,a[8][2]=7,a[8][3]=9;
    a[9][0]=2; a[9][1]=6,a[9][2]=8;
    for(int status=1;status<=(1<<9)-1;status++)
    {
        memset(m,0,sizeof(m));
        memset(light,0,sizeof(light));
        int b=1;
        for(int i=1;i<=9;i++)
        {
            //处理开灯的情况 
            if(status&b) m[9-i+1]=1;
            b*=2;
        } 
        /*
        for(int i=1;i<=9;i++)
        {
            cout<<m[i];
        }
        cout<<endl;
        */
        //根据规则处理灯 
        for(int i=1;i<=9;i++)
        {
            if(m[i])
            {
                for(int k=1;k<=a[i][0];k++)
                {
                    int idx=a[i][k];
                    light[idx]=1-light[idx];    
                }
            }
        }
        int sum=0;
        for(int i=1;i<=9;i++) sum+=light[i];
        if(sum==4) res.push_back(status); 
    }
    for(int i=0;i<res.size();i++)
    {
        int status=res[i];
        //cout<<status<<endl;
        memset(m,0,sizeof(m)); 
        int b=1;
        for(int k=1;k<=9;k++)
        {
            //处理开灯的情况 
            if(status&b) m[9-k+1]=1;
            b*=2;
        }
        for(int k=1;k<=9;k++) cout<<m[k];
        if(i+1!=res.size())  cout<<endl;
    }
    return 0;
}