枚举算法之——1813:熄灯问题

作者:admin|日期:2019-02-14|热度:

题目描述

有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。 请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。根据上面的规则,我们知道1)第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次;2)各个按钮被按下的顺序对最终的结果没有影响;3)对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯
原题链接:NOI / 2.1基本算法之枚举——1813:熄灯问题

解题思路:

因为每个按键有两种状态,一共30个按键,如果全部枚举,一共有2^30个结果,肯定超时。那怎么优化呢,其实,我们只要枚举第一行的64种情况就可以了(2^6=64),因为在处理第二行的时候,只要看第一行有多少个灯没灭就行,因为如果第一行灭掉了的灯,再被第二行点亮的话,结果显然是错的,所以第二行的任务就是把第一行没灭掉的灯灭掉。
第一行有0到63一共64种情况:对应二进制数字为:000000-111111,涵盖了6个灯的所有可能组合,所以用2进制比较方便处理。
三个函数说明:
void p(int n,int m)——此函数根据m解码第n行的开关状态,比如m=41,n=0,则s[0]=1 0 1 0 0 1。
int c(int n)——此函数计算第n行的灯的状态,转换成一个整数,做为下一行的开关状态解码。比如第0行,根据l[0]和s[0]的状态计算6个灯的状态为1 1 0 1 0 1,等于10进制的53,把它传给下一行的p函数处理,依此类推,如果最后一行6个灯都是灭的(即返回0),则输出解,否则枚举下一个。

参考代码:

#include<bits/stdc++.h>
using namespace std;
int l[5][6],s[5][6];

int c(int n){
    int x,ans=0;
    for(int i=0;i<6;i++){
        x=l[n][i]+s[n][i];
        if(i-1>=0) x+=s[n][i-1];
        if(i+1<6) x+=s[n][i+1];
        if(n-1>=0) x+=s[n-1][i];
        ans=(ans<<1)+(x%2);
    }
    return ans;
}
void p(int n,int m){
    int x;
    for(int i=0;i<6;i++){
        x=m;
        x=(x>>5-i)&1;
        s[n][i]=x;
    }
}
void print(){
    for(int i=0;i<5;i++){
        for(int j=0;j<6;j++)    cout<<s[i][j]<<' ';
        cout<<endl;
    }
}
int main(){
    int n;
    for(int i=0;i<5;i++)
        for(int j=0;j<6;j++)    cin>>l[i][j];
    for(int i=0;i<=63;i++){
        n=i;
        for(int j=0;j<5;j++){
            p(j,n);
            n=c(j);
        }
        if(n==0){
            print();
            return 0;
        }                        
    }    
    return 0;
}

再附一个超时的搜索算法:

#include<bits/stdc++.h>
using namespace std;
int l[6][7],s[6][7];
void print(){
    for(int i=0;i<5;i++){
        for(int j=0;j<6;j++)
            cout<<s[i][j]<<' ';
        cout<<endl;
    }
}
bool judge(){
    int n,x,y;
    for(int i=0;i<5;i++){
        for(int j=0;j<6;j++){
            n=l[i][j]+s[i][j];
            if(j-1>=0) n+=s[i][j-1];
            if(j+1<6) n+=s[i][j+1];
            if(i-1>=0) n+=s[i-1][j];
            if(i+1<5) n+=s[i+1][j];
            if(n&2>0) return false;
        }
    }
    return true;
}
void search(int n){
    int i,j;
    if(n==30){
        if(judge())    print();
    }else{
        i=n/6;
        j=n%6;
        s[i][j]=1;
        search(n+1);
        s[i][j]=0;
        search(n+1);
    }
}

int main(){
    for(int i=0;i<5;i++)
        for(int j=0;j<6;j++)
            cin>>l[i][j];
    memset(s,0,sizeof(s));
    search(0);
}