OpenJudge2811:熄灯问题（枚举）

熄灯问题

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

大致思路

枚举第一行的操作，在每个的下一行全部将上一行的没有关闭的灯熄灭，最后根据最后一行的灯的状态来判断是否完成。

//定义两个数组分别记录初始状态和操作
//定义函数判断当前位置经过各种操作后的灯的状态
//枚举第一行的所有情况
//每一行都将上一行未熄灭或者点亮的灯熄灭
//操作完成后判断最后一行是否全部熄灭，若没有则继续枚举

题解代码

#include<bits/stdc++.h>
using namespace std;

int arr[10][10];
int op[10][10];

int getState(int x, int y)
{
    return (arr[x][y] + op[x][y] + op[x+1][y] + op[x-1][y] + op[x][y+1] + op[x][y-1]) & 1;
}

void print()
{
    //输出最终的操作矩阵
    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 6; j++){
            cout << op[i][j] << ' ';
            //cout << getState(i, j) << ' ';
        }
        cout << endl;
    }
}

bool check()
{
    //检查最后一行是否为全0
    for(int i = 1; i <=6; i++){
        if(getState(5, i) == 1) return false;
    }
    return true;
}

bool findFirst(int n)
{
    //对第一行进行操作并对后续行完成后续操作
    int cnt = 1;
    while(n){
        op[1][cnt] = n & 1;
        n >>= 1;
        cnt++;
    }
    for(int i = 2; i <= 5; i++){
        for(int j = 1; j <= 6; j++){
            if(getState(i-1, j) == 1) op[i][j] = 1;
            else op[i][j] = 0;
        }
    }
    /*print();
    cout << "----------\n";*/

    return check();
}

int main(){
    memset(arr, 0, sizeof arr);

    for(int i = 1; i <= 5; i++){
        for(int j = 1; j <= 6; j++){
            cin >> arr[i][j];
        }
    }

    for(int i = 0; i < 64; i++){// 总共有6列灯，2^6种情况
        memset(op, 0, sizeof op);
        if(findFirst(i)){
            print();
            break;
        }
    }

    return 0;
}