费解的开关

题目描述

$5 \times 5$ 的灯阵，每次选择一个灯，把它和上下左右的灯状态翻转。 $1$ 表示亮， $0$ 表示灭。给定 $n$ 个初始局面，求每个局面在不超过 6 次操作内使所有灯变亮的最少步数；无法做到输出 $-1$ 。

思路

枚举第一行的 32 种按法；第一行确定后，上一行未亮的列唯一决定下一行必须按的开关，逐行递推。用 5 位二进制表示一行，位运算完成翻转，过程中累计步数超过 6 就剪枝。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 09:19
# update_at: 2026-10-01 09:19

import sys

ALL_LIGHTS = 0b11111  # 5 盏灯全亮的状态编码：低 5 位全为 1
INF = 100             # 哨兵：表示在步数限制内不可行


def simulate_first_row(grid: list[int], op0: int) -> int:
    """给定第一行的操作方案 op0，递推后续各行并返回使全部灯变亮所需的最少步数。"""
    rows = list(grid)
    press_count = 0

    # 第一行执行 op0
    curr_op = op0
    for r in range(5):
        press_count += curr_op.bit_count()
        if press_count > 6:
            return INF
        # 当前行自身及左右受 curr_op 影响
        rows[r] ^= curr_op ^ ((curr_op << 1) & ALL_LIGHTS) ^ (curr_op >> 1)
        # 下一行受影响
        if r + 1 < 5:
            rows[r + 1] ^= curr_op
            # 下一行的操作完全由当前行未亮的灯唯一确定
            curr_op = (~rows[r]) & ALL_LIGHTS
        else:
            # 最后一行已无下一行可操作，若仍有灯未亮则该方案不合法
            if rows[r] != ALL_LIGHTS:
                return INF

    return press_count


def min_steps_for_board(grid: list[int]) -> int:
    """枚举第一行的所有 32 种按键可能，返回 <= 6 的最少步数；若无法达成返回 -1。"""
    best = min((simulate_first_row(grid, op) for op in range(32)), default=INF)
    return best if best <= 6 else -1


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    out: list[int] = []

    for _ in range(n):
        # 每行 5 个字符转为 5 位二进制整数（第 c 位对应列 c）
        grid = [
            sum((int(ch) << c) for c, ch in enumerate(next(data).decode()))
            for _ in range(5)
        ]
        out.append(min_steps_for_board(grid))

    print('\n'.join(map(str, out)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:53
 * update_at: 2026-10-06 10:53
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int ALL = 0b11111; // 5 盏灯全亮的状态
const int INF = 100;     // 超过 6 步的哨兵

int rows[6]; // 5x5 盘面每行压缩为一个 5 位整数

// 给定第一行操作 op0，递推得到最少步数；不可行返回 INF
int simulate(int op0) {
    int cur = op0;
    int steps = 0;
    for (int r = 0; r < 5; ++r) {
        steps += __builtin_popcount(cur);
        if (steps > 6) return INF;
        // 当前行自身及左右邻居被翻转
        rows[r] ^= cur ^ ((cur << 1) & ALL) ^ (cur >> 1);
        if (r + 1 < 5) {
            rows[r + 1] ^= cur;          // 下一行受当前行操作影响
            cur = (~rows[r]) & ALL;      // 当前行灭灯位置决定下一行必须按的开关
        } else {
            if (rows[r] != ALL) return INF; // 最后一行仍有灭灯则方案失败
        }
    }
    return steps;
}

int solve_one() {
    int backup[6];
    int ans = INF;
    for (int op0 = 0; op0 < 32; ++op0) {
        memcpy(backup, rows, sizeof(rows));
        ans = min(ans, simulate(op0));
        memcpy(rows, backup, sizeof(rows));
    }
    return ans <= 6 ? ans : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    while (n--) {
        string s;
        for (int r = 0; r < 5; ++r) {
            cin >> s;
            int mask = 0;
            for (int c = 0; c < 5; ++c)
                if (s[c] == '1') mask |= (1 << c);
            rows[r] = mask;
        }
        cout << solve_one() << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码