摘要
Title: 116. 飞行员兄弟
Tag: 二进制枚举
Memory Limit: 64 MB
Time Limit: 1000 ms

116. 飞行员兄弟

题意

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。
但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
思路

可以注意到数据范围只有4，可以进行全排列，将二维数组拉长为一维01串，枚举每个开关的状态，进行判断即可
ps: 由于n=16, 复杂度为 $O(2^16 * 16)$ ，可以接受，但是再大点就要采取DFS求全排列了，复杂度为 $O(2^16)$

代码

'''
Author: NEFU AB-IN
Date: 2022-03-22 17:49:04
FilePath: \ACM\Acwing\116.py
LastEditTime: 2022-03-22 17:55:34
'''
from copy import deepcopy

g = []


def f(x, y):
    if g[x][y] == '+':
        g[x][y] = '-'
    else:
        g[x][y] = '+'


def change(x, y):
    for i in range(4):
        f(i, y)
    for i in range(4):
        f(x, i)
    f(x, y)


for i in range(4):
    g.append(list(input()))

res = []
minn = int(2e9)

backup = deepcopy(g)

for i in range(1 << 16):
    # if i == 53261:
    #     ddd = 1
    ans, flag = [], 0
    g = deepcopy(backup)
    for j in range(16):
        if i & 1 << j:
            x, y = j // 4, j % 4
            change(x, y)
            ans.append([x, y])
    for i in range(4):
        for j in range(4):
            if g[i][j] == '+':
                flag = 1
                break
        if flag: break

    if flag == 0 and len(ans) <= minn:
        if len(ans) < minn:
            res = []
        res.append(ans)
        minn = len(ans)
        
for ans in res:
    print(len(ans))
    for x, y in ans:
        print(x + 1, y + 1)

116. 飞行员兄弟

题意

思路

代码