说明

这段代码是解决“扩展版熄灯游戏”问题的程序。游戏的目标是通过按下按钮使得所有灯都熄灭。每个按钮按下会反转自身及其相邻按钮的状态。程序通过枚举第一行的所有可能按钮状态，然后逐行推导出其他行的按钮状态，最终检查是否所有灯都被熄灭。

算法标签

• 枚举法：枚举第一行的所有可能按钮状态。
• 模拟：模拟按钮按下后的灯光变化。
• 递推：根据上一行的灯光状态递推下一行的按钮状态。

解题思路

1. 问题分析：每个按钮按下会影响自身及其上下左右的按钮状态。目标是通过按下某些按钮使得所有灯熄灭。
2. 关键观察：一旦第一行的按钮状态确定，后续每一行的按钮状态可以通过上一行的灯光状态唯一确定。因为每一行的按钮状态必须保证上一行的灯全部熄灭。
3. 算法选择：
   • 枚举第一行的所有可能按钮状态（共2^6=64种可能）。
   • 对于每种枚举的状态，逐行计算后续按钮状态，确保上一行的灯全部熄灭。
   • 检查最后一行是否全部熄灭，若成功则输出结果。

分析

1. 输入处理：读取测试用例数量及每个测试用例的初始灯光状态。
2. 枚举第一行：使用二进制枚举法生成第一行的所有可能按钮状态。
3. 递推计算：
   • 对于每一行，根据上一行的灯光状态计算当前行的按钮状态，确保上一行的灯全部熄灭。
   • 递推公式：press[i][j] = (b[i-1][j] + press[i-1][j] + press[i-1][j-1] + press[i-2][j] + press[i-1][j+1]) % 2
4. 检查结果：验证最后一行是否全部熄灭，若成功则输出按钮状态矩阵。

实现步骤

1. 初始化：读取输入数据，初始化灯光状态矩阵b和按钮状态矩阵press。
2. 枚举第一行：通过二进制枚举生成第一行的所有可能按钮状态。
3. 递推计算：
   • 从第二行开始，根据上一行的灯光状态和按钮状态计算当前行的按钮状态。
   • 确保上一行的灯全部熄灭。
4. 验证结果：检查最后一行是否全部熄灭，若成功则输出按钮状态矩阵。
5. 输出结果：按格式输出每个测试用例的结果。

代码解释

• 输入处理：使用scanf读取测试用例数量和每个测试用例的初始灯光状态。
• 枚举第一行：通过循环和进位操作生成第一行的所有可能按钮状态。
• 递推计算：使用嵌套循环计算每一行的按钮状态，确保上一行的灯熄灭。
• 验证结果：检查最后一行是否全部熄灭，若成功则输出按钮状态矩阵。
• 输出格式：按题目要求输出“PUZZLE #m”及对应的按钮状态矩阵。

通过这种方法，程序能够高效地找到解决每个谜题的按钮按下方案。

代码

/* POJ1222 UVA1560 LA2561 ZOJ1354 EXTENDED LIGHTS OUT */

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 5, M = N + 1;
int b[N + 1][M + 2], press[N + 1][M + 2];

bool solve() {
    for(int i = 2 ; i <= N; i++) {
        for(int j = 1 ; j <= M; j++) {
            press[i][j] = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2;

        }
    }
    /* 检查最后一行是否都已经关灯 */
    for(int j = 1 , i = M; j <= M ; j++) {
        int t = (b[i - 1][j] + press[i - 1][j] + press[i - 1][j - 1] + press[i - 2][j] + press[i - 1][j + 1]) % 2;
        if(t)return false;
    }
    return true;
}

int main()
{
    int t, caseno = 0;
    scanf("%d", &t);
    while(t--) {
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= M; j++)
                scanf("%d", &b[i][j]);

        memset(press, 0, sizeof(press));
        bool flag = false;
        while(!flag) {
            if((flag = solve())) break;

            /* 对于第1行进行枚举，000000-111111，采用加1方式实现 */
            int t = 1;
            press[1][t]++;
            while(press[1][t] > 1) {
                press[1][t] = 0;
                t++;
                press[1][t]++;
            }
            if(t > M) break;
        }

        printf("PUZZLE #%d\n", ++caseno);
        if(flag)
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= M ; j++) {
                    if(j > 1) printf(" ");
                    printf("%d", press[i][j]);
                }
                printf("\n");
            }
    }

    return 0;
}