摘要
Title: 95. 费解的开关
Tag: 位运算、递推、二进制枚举
Memory Limit: 64 MB
Time Limit: 1000 ms

95. 费解的开关

题意

见原题
思路

结论：当第一行的状态固定时，整个矩阵的状态就固定了
也就是说，第i行的状态是有第i-1行的状态决定的

所以
- 我们就可以用二进制枚举枚举第一行的状态，1代表动这个开关，0代表不动
- 其次，从第1行枚举到第4行，如果 $g[i][j]=0$ ，说明必须由 $g[i + 1][j]$ 变化，使得 $g[i][j]=1$
- 最后判断第5行，如果答案不大于6，且第五行全是1，就更新答案
ps: 可以单独列出一个函数，用来表示上下左右的灯变化状态

代码

'''
Author: NEFU AB-IN
Date: 2022-03-21 19:53:58
FilePath: \ACM\Acwing\95.py
LastEditTime: 2022-03-21 20:33:08
'''
from copy import deepcopy

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def turn(x, y):
    g[x][y] ^= 1
    for id in range(4):
        idx = x + dx[id]
        idy = y + dy[id]
        if idx >= 0 and idx < 5 and idy >= 0 and idy < 5:
            g[idx][idy] ^= 1

n = int(input())
for _ in range(n):
    g = []
    for i in range(5):
        g.append(list(map(int, input())))

    backup = deepcopy(g)
    minn = int(1e18)
    for op in range(1 << 5):
        flag, ans = 0, 0
        g = deepcopy(backup)
        for j in range(5):
            if op & 1 << j:
                ans += 1
                turn(0, j)
        for i in range(4):
            for j in range(5):
                if g[i][j] == 0:
                    turn(i + 1, j)
                    ans += 1
        for j in range(5):
            if g[4][j] == 0:
                flag = 1
                break
        if flag == 0 and ans <= 6:
            minn = min(minn, ans)
    if minn == int(1e18):
        print(-1)
    else:
        print(minn)
    if _ < n - 1:
        b = input()

95. 费解的开关

题意

思路

代码