ACM暴力枚举 | 熄灯问题
Mr_zwX / 2020-10-28 / 算法 / 阅读量 36

题目描述

暴力枚举求解熄灯问题这是个很好的题目!!!写到这道题感觉很有意思,不论从思路还是代码上,都需要总结。

有一个5*6的矩阵,每个位置上都有一盏灯和一个按钮,每按一次按钮,这盏灯及周围四个相邻位置的灯都会改变一次,如图:

请输入图片描述

请写一个程序,输入T组数据,每组数据中输入一个0 1矩阵,输出一个矩阵,表示出哪些按钮是需要操作的?恰好使得所有灯都熄灭!

请输入图片描述

题解

这题乍一看蛮玄的,细细分析还是发现有规律可循...
从第一行往下看,如果有灯开着,那么我们需要按它对应的下一行按钮,以此类推,某一行有灯亮着,按下一行对应位置按钮...那么就类推到了最后一行,现在就需要判断最后一行是否都熄灭了...
为了处理二维数组比较方便,建二维数组的时候扩充到边缘,让存储值的区域下标从1开始比较好

请输入图片描述

代码

#include<iostream>
using namespace std;
int puzzle[6][8],press[6][8];
//对状态进行判断 
bool guess(void){
    int i,j;
    //下一行的对应位置该怎么操作? 
    for(i=1;i<5;i++){
        for(j=1;j<7;j++){
            press[i+1][j]=(puzzle[i][j]+press[i][j]+press[i-1][j]+press[i][j-1]+press[i][j+1])%2;           
        }
    }
    //判断最后一行熄灭了吗?
    for(j=1;j<7;j++){
        if((press[5][j-1]+press[5][j]+press[5][j+1]+press[4][j])%2!=puzzle[5][j]) return false;
    } 
    return true;
}
//枚举第一行的各种情况 
void enumate(void){
    int j;
    for(j=1;j<7;j++){
        press[1][j]=0;
    }
    while(guess()==false){//如果最后一行没熄灭才执行下一项枚举,最后一行都熄灭了就在main直接打印press 
        //这里枚举每一位0 1值很重要 有2^6中情况
        press[1][4]++;
        j=1;
        while(press[1][j]>1){
            press[1][j]=0;
            j++;
            press[1][j]++;
        }
    }
}

int main(){
    int T,t,i,j;
    cin>>T; 
    //清零左右边栏
    for(i=0;i<6;i++) press[i][0]=press[i][7]=0;
    //清空上边栏
    for(j=1;j<7;j++) press[0][j]=0;
    for(t=1;t<=T;t++){
        //读入puzzle数组
        for(i=1;i<6;i++){
            for(j=1;j<7;j++){
                cin>>puzzle[i][j];
            }
        }
        enumate();
        cout<<"PUZZLE #"<<t<<endl;
        //打印press数组
        for(i=1;i<6;i++){
            for(j=1;j<7;j++){
                cout<<press[i][j]<<" ";
            }
            cout<<endl;
        }       
    }
    return 0;
}

样例输出

2
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
PUZZLE #1
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
//这里其实没有换行哦
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1

--------------------------------
支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
1 + 9 =
沙发在此!快来做第一个评论的人~