n*m灯泡网格求最少关灯切换次数的解法思路咨询

这是经典的关灯问题，核心前提是同一位置切换2次等价于不切换，因此每个位置最多只需操作1次，我们只需在所有合法的0/1操作矩阵中，找到总操作次数最小的方案即可。

核心求解逻辑 #

• 固定首行操作策略：首行每个位置可选择按或不按，共2^m种可能，当m≤20时可直接枚举所有情况。
• 后续行操作完全固定：首行操作确定后，只有当*上一行对应位置的灯泡处于点亮状态（'O'）*时，才需要按下当前行该位置的开关。这是因为后续行的操作不会影响到上一行的灯泡，这是最后一次能将上一行灯泡熄灭的机会。
• 有效性校验：遍历完所有行后，检查最后一行是否全部熄灭。如果全灭则当前策略合法，记录总操作次数；否则当前策略无效。
• 最终返回所有合法策略的最小操作次数，无合法策略则返回-1。

优化方案 #

• 若n<m，可先将网格转置，枚举长度更短的行的操作状态，将时间复杂度降到O(2^min(n,m) * n*m)
• 状态可以用位运算压缩，无需额外拷贝整个网格，大幅提升运行效率
• 当min(n,m)＞20时，可改用高斯消元解异或方程组求解，时间复杂度为O((n*m)^3)，适合小规模稠密网格

参考伪代码 #

def min_flips(grid):
    n = len(grid)
    m = len(grid[0])
    min_cnt = float('inf')
    dirs = [(-1,0), (1,0), (0,-1), (0,1), (0,0)] # 四邻域+当前位置

    def flip(g, x, y):
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                g[nx][ny] = 'O' if g[nx][ny] == 'X' else 'X'

    # 枚举首行所有操作状态
    for mask in range(1 << m):
        temp = [row.copy() for row in grid]
        cnt = 0
        # 执行首行操作
        for j in range(m):
            if mask >> j & 1:
                flip(temp, 0, j)
                cnt += 1
        # 执行后续行操作
        for i in range(1, n):
            for j in range(m):
                if temp[i-1][j] == 'O':
                    flip(temp, i, j)
                    cnt += 1
        # 校验最后一行是否全灭
        if all(c == 'X' for c in temp[-1]):
            min_cnt = min(min_cnt, cnt)
    
    return min_cnt if min_cnt != float('inf') else -1

内容的提问来源于stack exchange，提问作者Aniket Katakdhond