1813:熄灯问题

2018-01-15 17:14:33


1813:熄灯问题

总时间限制: 1000ms 内存限制: 65536kB

描述 有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。

在上图中,左边矩阵中用X标记的按钮表示被按下,右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮,直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果。在下图中,第2行第3、5列的按钮都被按下,因此第2行、第4列的灯的状态就不改变。

请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。根据上面的规则,我们知道1)第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次;2)各个按钮被按下的顺序对最终的结果没有影响;3)对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯。

输入 5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。0表示灯的初始状态是熄灭的,1表示灯的初始状态是点亮的。

输出 5行组成,每一行包括6个数字(0或1)。相邻两个数字之间用单个空格隔开。其中的1表示需要把对应的按钮按下,0则表示不需要按对应的按钮。

样例输入

0 1 1 0 1 0

1 0 0 1 1 1

0 0 1 0 0 1

1 0 0 1 0 1

0 1 1 1 0 0

样例输出

1 0 1 0 0 1

1 1 0 1 0 1

0 0 1 0 1 1

1 0 0 1 0 0

0 1 0 0 0 0

题目分析:

第一想法,枚举所有可能的按钮(开关)状态,对每一个状态计算最后灯的情况,看是否熄灭,每个按钮有2种状态,一共有30个开关,则状态数为2的30次方,会超时!

枚举局部!如果存在某个局部,一旦这个局部的状态被确定,那么剩余其他部分的状态只能是确定的一种!

怎么局部呢?经过观察,第1行就是这样的一个局部!只要确定了第一行的状态确定之后,作用之后,会导致第1行的某些灯是亮的,某些灯是灭的。!!:要熄灭第一行某个亮着的灯(假设位于第i列)那么唯一的办法就是按下第二行第i列的开关!!(因为第一行的开关已经用过了,而第三行及其后的开关不会影响到第一行)

故为了使第1行的灯全部熄灭,第2行的合理开关状态就是唯一的!依次类推!若第5行的灯没有全部熄灭,则此方案是不合理的,故改变第1行的开关方案。

如何优化?枚举第一列,状态数是2的5次方。此时可以用一个int类型的变量,从0变到63,第1行的开关有6个,相当于有6个比特的所有0,1组合,这时这个变量的每一个取值就对应每一个开关的状态!

代码:

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int a[6][8];//初始位置
    int init[6][8];//存储按下的按钮
    bool guess()
    //寻找出第一行中的各种取值所对应的结果,再通过数据来判定相应的结果和输出
    {
        for(int i=1; i<5; i++)
            for(int j=1; j<7; j++)
                init[i+1][j]=(a[i][j]+init[i][j]+init[i-1][j]+init[i][j-1]+init[i][j+1])%2;
    //当init[1][j]的取值为1时,init[2][j]位置上的数也为1;反之亦然。
        for(int i=1; i<7; i++)
    //判断最后一行是否熄灭
            if((init[5][i-1]+init[5][i]+init[5][i+1]+init[4][i])%2!=a[5][i])
                return (false);
        return (true);
    }
    void enumate()
    // 进行枚举的过程,找出64种可能情况中找出数据中对应的输出
    {
        for(int i=1; i<7; i++)
            init[1][i]=0;
    //对第一行进行初始化
        while(guess()==false)
        {
            init[1][1]++;
            int i = 1;
            while(init[1][i]>1)
            {
    //找到答案就返回,否则继续进行搜索
                init[1][i]=0;
                i++;
                init[1][i]++;
            }
        }
        return ;
    }
    int main()
    {
        for(int i=0; i<6; i++)
            a[i][0]=0;
        for(int i=1; i<7; i++)
            a[0][i]=0;
    //由于在枚举过程中不会用到a[0]和a[i]两种边界值,因此将其初始化为0
        for(int i=1; i<6; i++)
            for(int j=1; j<7; j++)
                cin >> a[i][j];
    // 开始枚举第一行的64种可能取值
        enumate();
    // 通过枚举找到正确答案,然后按标准格式输出
        for(int i=1; i<6; i++)
        {
            for(int j=1; j<7; j++)
                cout << init[i][j] << " ";
            cout << endl;
        }
        return 0;
}