P4711 拉灯（提高）

解题思路

这是经典的 5×5 灭灯游戏：25 盏灯排成 5 行 5 列，按一盏灯，它自己和上下左右相邻的四盏灯都会改变状态（亮的变灭、灭的变亮）。题目要求判断 6 步之内能不能把所有灯都点亮，并且输出最少需要的步数，做不到就输出 -1。

先想清楚一个关键性质：一盏灯按两次等于没按，所以任何最优方案里，每盏灯要么不按、要么按一次。也就是说，一个"方案"就是一个由 25 个 0/1 组成的按灯矩阵。

再想清楚第二个关键性质：只要确定了第一行哪几盏灯要按（第一行 5 盏灯，按或不按一共 2^5=32 种情况），后面每一行怎么按就被"逼"出来了：

• 当第一行按完之后，看第二行的灯。如果第二行某一盏灯的上面（第一行那个位置）还是灭的，那这盏灭灯就只能靠按第二行这一盏来救，没有其他选择。
• 就这样一路推下去：第二行的按法决定第三行，第三行决定第四行，第四行决定第五行。
• 全部按完之后，检查最后一行是否全部变亮。如果全亮，说明这个第一行方案成功，记录下总共按灯的次数。

于是算法就是：枚举第一行的 32 种按法，每种按法唯一对应一个完整方案，在所有成功的方案里取按灯次数最少的一个。如果最小值不超过 6 就输出它，否则输出 -1。

这就像推多米诺骨牌：只要第一张牌倒的方向定了，后面每一张牌的倒下方向都是由前一张决定的，不需要再选择。

边界情况：按灯会越界，比如最左边一盏灯的"左邻居"是不存在的，代码里要用 ni、nj 判断是否还在 5×5 范围内，越界就忽略那个方向。

参考代码

// 拉灯：5x5灭灯游戏，判断6步内能否全亮并求最少步数
#include <cstdio>
int light[6][6]; // 初始灯的状态
int cur[6][6];   // 中间状态
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, -1, 1, 0, 0};
// 按第一行的按灯方案 mask 模拟，返回按灯次数，若最后一排不全亮返回很大的数
int solveByMask(int mask) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++) cur[i][j] = light[i][j];
    int cnt = 0;
    // 处理第一行：按 mask 的二进制位决定是否按灯
    for (int j = 0; j < 5; j++) {
        if ((mask >> j) & 1) {
            cnt++;
            for (int k = 0; k < 5; k++) {
                int ni = dx[k], nj = j + dy[k];
                if (ni >= 0 && ni < 5 && nj >= 0 && nj < 5) cur[ni][nj] ^= 1;
            }
        }
    }
    // 从第二行起：上面一行若还有灭的灯，只能在当前行按
    for (int i = 1; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (cur[i - 1][j] == 0) {
                cnt++;
                for (int k = 0; k < 5; k++) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < 5 && nj >= 0 && nj < 5) cur[ni][nj] ^= 1;
                }
            }
        }
    }
    // 检查最后一行是否全亮
    for (int j = 0; j < 5; j++)
        if (cur[4][j] == 0) return 1000;
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int t = 0; t < n; t++) {
        // 读入5行5个字符，跳过空格换行
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                char ch = getchar();
                while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = getchar();
                light[i][j] = ch - '0';
            }
        }
        int best = 1000;
        // 枚举第一行32种按灯方案
        for (int mask = 0; mask < 32; mask++) {
            int r = solveByMask(mask);
            if (r < best) best = r;
        }
        if (best <= 6) printf("%d\n", best);
        else printf("-1\n");
    }
    return 0;
}

复杂度分析

每组数据要枚举第一行的 32 种按法，每种按法要模拟 25 盏灯，所以单组数据大约是 32×25=800 次操作。一共有 n 组数据，总复杂度就是 O(n×32×25)，几乎可以看成 O(n)，速度极快。

空间方面，只用了一个 6×6 的初始灯状态数组和一个 6×6 的临时状态数组，以及几个方向数组，全部都是常数级别的空间，与输入规模无关。