02811: 熄灯问题

brute force, http://cs101.openjudge.cn/practice/02811

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

在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。

请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道

1）第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次；

2）各个按钮被按下的顺序对最终的结果没有影响；

3）对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前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

2020fall-cs101，曲诤博。题本来是很难的，还好题干中给了提示，最后的难点有两个，一个是如何生成 0，1 排列组合的所有 64 个 list，这里我用了迭代的方法，还有一个就是如何实现题干的方法，这里用了一下深拷贝，之后就没啥问题了。

2020fall-cs101，顾臻宜。解题思路：A 记开关实时亮暗，B记开关操作与否。一旦确定第1 行的操作，剩 余第2、3、4、5 行的操作就确定；枚举第1 行（共2^6^=64 种可能）。 小知识：二维数组需要深度拷贝：import copy；A=copy.deepcopy(X)。

X = [[0,0,0,0,0,0,0,0]]
Y = [[0,0,0,0,0,0,0,0]]
for _ in range(5):
    X.append([0] + [int(x) for x in input().split()] + [0])
    Y.append([0 for x in range(8)])    
X.append([0,0,0,0,0,0,0,0])
Y.append([0,0,0,0,0,0,0,0])

import copy
for a in range(2):
    Y[1][1] = a
    for b in range(2):
        Y[1][2] = b
        for c in range(2):
            Y[1][3] = c
            for d in range(2):
                Y[1][4] = d
                for e in range(2):
                    Y[1][5] = e
                    for f in range(2):
                        Y[1][6] = f
                        
                        A = copy.deepcopy(X)
                        B = copy.deepcopy(Y)
                        for i in range(1, 7):
                            if B[1][i] == 1:
                                A[1][i] = abs(A[1][i] - 1)
                                A[1][i-1] = abs(A[1][i-1] - 1)
                                A[1][i+1] = abs(A[1][i+1] - 1)
                                A[2][i] = abs(A[2][i] - 1)
                        for i in range(2, 6):
                            for j in range(1, 7):
                                if A[i-1][j] == 1:
                                    B[i][j] = 1
                                    A[i][j] = abs(A[i][j] - 1)
                                    A[i-1][j] = abs(A[i-1][j] - 1)
                                    A[i+1][j] = abs(A[i+1][j] - 1)
                                    A[i][j-1] = abs(A[i][j-1] - 1)
                                    A[i][j+1] = abs(A[i][j+1] - 1)
                        if A[5][1]==0 and A[5][2]==0 and A[5][3]==0 and A[5][4]==0 and A[5][5]==0 and A[5][6]==0:
                            for i in range(1, 6):
                                print(" ".join(repr(y) for y in [B[i][1],B[i][2],B[i][3],B[i][4],B[i][5],B[i][6] ]))

优化上面代码

def flip(lights, r, c):
    """翻转(r, c)位置及其上下左右的灯状态"""
    for dr, dc in [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0)]:
        nr, nc = r + dr, c + dc
        if 1 <= nr <= 5 and 1 <= nc <= 6:
            lights[nr][nc] ^= 1  # 异或操作更快更简洁

# 读取输入并初始化带边框的灯状态矩阵（6x8，四周补0）
lights = [[0]*8]
for _ in range(5):
    row = [0] + list(map(int, input().split())) + [0]
    lights.append(row)
lights.append([0]*8)


# 枚举第一行的所有可能操作（共 2^6 = 64 种）
found = False
for mask in range(64):
    # 复制原始灯状态和清空 press 状态
    current_lights = [row[:] for row in lights]
    current_press = [[0]*8 for _ in range(6)]

    # 根据 mask 设置第一行按钮是否按下
    for j in range(6):
        if (mask >> j) & 1:
            current_press[1][j+1] = 1
            flip(current_lights, 1, j+1)

    # 从第2行到第5行，根据上一行灯的状态决定本行按钮操作
    for i in range(2, 6):
        for j in range(1, 7):
            if current_lights[i-1][j] == 1:  # 上一行的灯还亮着
                current_press[i][j] = 1
                flip(current_lights, i, j)

    # 检查最后一行是否全灭
    if all(current_lights[5][j] == 0 for j in range(1, 7)):
        found = True
        # 输出答案
        for i in range(1, 6):
            print(' '.join(str(current_press[i][j]) for j in range(1, 7)))
        break

if not found:
    print("No solution found!")

算法思路回顾（正确性保证）

• 关键观察：一旦第一行的按钮按下方式确定，后续每一行的操作就唯一确定——必须把上一行还亮着的灯“压下去”。
• 所以只需枚举第一行的 2^6=64 种可能，模拟整个过程，看最后一行能否全灭。
• 时间复杂度：O(64×5×6)=O(1)，完全可以接受。

2020fall-cs101，李元锋。思路：最难的一题，暴力一定超时。从第一行开始，注意到如果要消除第一行的灯，必然要按它下面的灯，这样就可以把枚举情况降至 2^6^。先用 iterations模块生成所有 6个(0,1)组合的 list，然后根据 list判断下一步做什么，以此类推。最后生成答案即可。

2020fall-cs101，李宗远

from copy import deepcopy
from itertools import product
rmap = {0:1, 1:0}
matrix_backup = [[0] * 8] + [[0, *map(int, input().split()), 0] for i in range(5)] \
    + [[0] * 8]
    
for test in product(range(2), repeat=6):
    matrix = deepcopy(matrix_backup)
    triggers = [list(test)]  
    for i in range(1, 6):         
        for j in range(1, 7):
            if triggers[i - 1][j - 1]:
                matrix[i][j] = rmap[matrix[i][j]]
                matrix[i - 1][j] = rmap[matrix[i - 1][j]]
                matrix[i + 1][j] = rmap[matrix[i + 1][j]]
                matrix[i][j - 1] = rmap[matrix[i][j - 1]]
                matrix[i][j + 1] = rmap[matrix[i][j + 1]]
        triggers.append(matrix[i][1:7])
    if matrix[5][1:7] == [0, 0, 0, 0, 0, 0]:
        for trigger in triggers[:-1]:
            print(' '.join(map(str, trigger)))

我们称这 mn 个灯构成的方阵为棋盘。不妨设n不超过 m。

设操作 M 为：对于某一种初始棋盘，依次按第二列、第三列、.、第 m 列使得前 m-1 列的灯都熄灭，只留第 m列可能有灯还亮。时间复杂度：O(mn)

在一个本来全部熄灭的棋盘上，先任意按第一列的灯(一共 2^n 种按法)然后做操作 M，会在第 m 列得到一种亮/灭分布(一共也是 2^n种可能情形)

我们声称，操作 M 可以看成第一列的 2^n 种按灯方式($F_2$上的n维线性空间 W)到第 m 列的 2^n种亮/灭分布(F上的n维线性空间 W)的一个函数，目这个函数是一个线性映射。

1. 取V 的标准基，对其中每一个向量运行操作 M，得到W 中的n个向量。如1.果他们线性相关，则题目不可做。事实上，此时必存在一种棋盘无法被全部熄灭，而对于可以被全部熄灭的棋盘，熄灭方法也不唯一。这一步的复杂度为 m*n*n
2. 经过第一步之后，我们得到了这个线性映射的一个矩阵表示。如果题目可做的话，这个矩阵是可逆的。在 O(n^3)时间内，我们可以取它的逆。
3. 现在考虑原题，我们看到初始的棋盘，运行操作 M，并记录我们按下的所有灯(记为 X)。得到 W 中的一个向量。用第二步中取出的逆矩阵作用在这个向量上，得到V中的一个向量，记为 u。
4. 对u运行操作 M，并记录我们按下的所有灯(记为 Y)
5. x+u+Y 即为所求的按灯方式。

#费雨缪 20数学科学学院。Time Complexity: O(mn^2)
n = 5; m = 6
Board = [[0 for i in range(m+2)]]
for i in range(n):
    Board.append([0] + [int(x) for x in input().split()] + [0])
Board += [[0 for i in range(m+2)]]

Ans = [[0]*m for i in range(n)]

def click(i, j):
    Ans[i][j] = 1 - Ans[i][j]
    for x, y in [(i-1, j), (i, j-1), (i, j), (i, j+1), (i+1, j)]:
        Board[x+1][y+1] = 1 - Board[x+1][y+1]
    return

def play():
    for j in range(1, m):
        for i in range(n):
            if (Board[i+1][j] == 1):
                click(i, j)

play()
for i in range(n):
    if (Board[i+1][m] == 1):
        click(i, 0)

play()
for i in range(n):
    print(' '.join(str(x) for x in Ans[i]))

https://www.cnblogs.com/drzrunze/p/15618477.html 发现了一个熄灯问题的线代解法。

思路：枚举第一行的所有情况，在每个情况开始的时候重置grid，注意do也要重置。在第一行确定之后，下面每一行的操作都确定了，想让每一行的灯灭掉，必须按它正下方的开关，全部操作结束后检查最后一行是不是还有亮灯，若否则找到了答案。

# 张清州 24化学与分子工程学院
original_grid = [list(map(int, input().split())) for _ in range(5)]
def toggle(grid, x, y):
    grid[x][y] ^= 1  # 反转当前位置的灯
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 定义四个方向
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < 5 and 0 <= ny < 6:  # 确保索引不越界
            grid[nx][ny] ^= 1  # 反转邻居灯的状态

for mask in range(64):  # 枚举所有第一行灯的操作（2^6 = 64种）
    grid = [row[:] for row in original_grid]  # 复制原始网格
    do = [[0] * 6 for _ in range(5)]  # 记录每个灯是否被点击的操作矩阵

    for j in range(6):  # 枚举第一行的每一列
        if (mask >> j) & 1:  # 如果第j列被选择按下开关
            toggle(grid, 0, j)  # 点击第一行的第j列
            do[0][j] = 1  # 记录操作

    for i in range(1, 5):  # 对于第二行到第五行，根据上一行的状态决定操作
        for j in range(6):
            if grid[i-1][j] == 1:  # 如果上一行的灯是亮着的（需要按下开关）
                toggle(grid, i, j)  # 按下当前行的第j列的开关
                do[i][j] = 1  # 记录操作

    # 如果最后一行的灯全灭，说明找到了解决方案
    if all(grid[4][j] == 0 for j in range(6)):
        for row in do:
            print(" ".join(map(str, row)))  # 输出操作序列
        break  # 找到答案后跳出循环

​ (问的GPT，这个游戏从小就没想出来)题目有提示是上一行的灯可以通过操作下一行对应位置来关闭，gpt说可以对第一行开关灯共64种情况枚举，每一种情况会造成一种第一行的灯的初始开关状态，接着按题目提示的方式对后续关灯的操作方式是唯一的。自己想不到。

​ 其中在第一行的64种gpt使用的位运算来转换成0和1数值串来填充，很巧。

#GPT
dx,dy=[0,0,-1,1,0],[0,-1,0,0,1]
def press(light,x,y):
    for i in range(5):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<5 and 0<=ny<6:
            light[nx][ny]^=1 #异或，0^1=1,1^1=0
def doit():
    for first_row in range(64):
        s=[row[:] for row in light]  #不能用.copy()->仅用于一维列表
        solution=[[0]*6 for _ in range(5)]
        for j in range(6):   #第一行有64种开关方式，逐一遍历
            if (first_row >> j)&1:
                solution[0][j]=1
                press(s,0,j)

        for i in range(1,5):
            for j in range(6):
                if s[i-1][j]==1: #根据上一行开着的灯按下一行的按钮
                    solution[i][j]=1
                    press(s,i,j)

        if all(s[4][j]==0 for j in range(6)): #检查最后一行是不是已经熄灭
            for i in solution:
                print(*i)

light=[[int(i) for i in input().split()] for _ in range(5)]
doit()

感觉这题就是线性代数，总共有30*30的转移矩阵A。由于开关按两次是一样的，因此可以直接算如何从全暗到输入的状态，答案相同。得到的是线性方程组Ax=b，其中x待解，b是现在的状态。需要特别注意的是这个是在线性空间{0, 1}和加法a plus b=(a+b)%2下的方程组，因此在消元的时候要%2

如果用numpy会短很多，虽然oj不让用就是了

# 陈虹骏 24物理学院
from copy import deepcopy#其实不需要deepcopy
n=5
m=6
b=[]
def elim(list0, list1, i):
    s=list1[i]/list0[i]
    for k in range(n*m+1):
        list1[k]-=list0[k]*s
        list1[k]=round(list1[k])
        list1[k]%=2
        
for i in range(n):
    b+=list(map(int, input().split()))
#得到转移矩阵（系数矩阵）
mat=[[0 for i in range(m*n)] for j in range(m*n)]
for i in range(m*n):
    mat[i][i]=1
    if i%m!=0:
        mat[i][i-1]=1
    if i%m!=m-1:
        mat[i][i+1]=1
    if i//m!=0:
        mat[i][i-m]=1
    if i//m!=n-1:
        mat[i][i+m]=1
#得到增广矩阵
a=[]
for i in range(m*n):
    a.append([])
    a[i]=mat[i]+[b[i]]
#高斯消元
for i in range(n*m):
    #寻找主元
    for j in range(i, n*m):
        if a[j][i]!=0:
            a[i], a[j]=a[j], a[i]
            break
        
    #消元
    for j in range(i+1, n*m):
        elim(a[i], a[j], i)
#回代
for i in range(n*m-1, -1, -1):
    a[i][n*m]/=a[i][i]
    a[i][i]=1
    
    for j in range(0, i):
        a[j][n*m]-=a[j][i]*a[i][n*m]
        a[j][i]=0

#得到解
ans=[]
for i in range(n*m):
    ans.append(int(a[i][n*m])%2)
#输出
for i in range(n):
    print(*ans[m*i:m*(i+1)])

#小加强版，允许自由设置行数和列数。并且在遇到多解的问题时会算出所有的解。其实还可以再优化，算行和算列是等价的，因此应该算行数和列数中小的那一个，枚举情况数为2**min(m,n)
# 李冠黎 24工学院
import copy
result=[]
def dfs(tmp,k):
    global result
    if k==n:
        act=[tmp]+[[0]*n for _ in range(m-1)]
        if calculate(act):
            result.append(copy.deepcopy(act))
        return
    else:
        for i in range(2):
            tmp.append(i)
            dfs(tmp,k+1)
            tmp.pop()

def calculate(act):
    ext=copy.deepcopy(mtr)
    for j in range(n):
        open_light(0,j,act,ext)
    for i in range(m-1):
        act[i+1]=copy.deepcopy(ext[i])
        for j in range(n):
            open_light(i+1,j,act,ext)
    if check(ext):
        return True
    else:
        return False

def check(ext):
    for i in range(m):
        for j in range(n):
            if ext[i][j]==1:
                return False
    return True

def open_light(x,y,act,ext):
    if act[x][y]==1:
        ext[x][y]=abs(ext[x][y]-1)
        for i in range(4):
            tx,ty=x+dic[i][0],y+dic[i][1]
            if 0<=tx<m and 0<=ty<n:
                ext[tx][ty] = abs(ext[tx][ty] - 1)

dic=[[0,1],[0,-1],[1,0],[-1,0]]
m,n=5,6
mtr=[list(map(int,input().split())) for _ in range(m)]

dfs([],0)

for _ in range(len(result)):
    for i in range(len(result[_])):
        print(*result[_][i])
    print()