Python 版题解
原本我只写了 Python 的枚举版本,但在题解中看到了 极棚灰 大佬的数学题解,直呼妙哉!以此写写自己对大佬题解的理解 orz
题目描述
给定 $4 \times 4$ 初始开关状态,当改变某个开关状态时,其所在行列的开关也会改变状态。希望最终开关状态为全 -
(全开)。
算法 1
大佬数学巧解
题目中没有提到无解的情况,也就是说,所有(至少测试数据)的开关状态都能转变为全 -
状态(下面称为$\color{red}{最终状态}$)。因此我们可以反过来思考,在最终状态下,每个开关至多改变一次,如何恢复到初始状态?
这需要我们思考开关状态改变对整体的影响。
改变 1 个开关时
如下所示,对于最终状态,当我们任意改变某个开关(例如 [1,1]
),可以观察到,其所在行列的 +
总数是奇数;而未改变开关(除 [1,1]
之外的所有开关)所在行列的 +
总数是偶数
---- ++++
---- -> +---
---- +---
---- +---
改变 2 个开关时
在上面的基础上,我们再任意改变一个开关状态。可以观察到,
a. 若第二个开关与第一个开关同行或同列(例如 [1,3]
),则会使第一个开关所在行列的 +
总数少 4;
b. 若第二个开关与第一个开关不同行列(例如 [3,3]
),则会使第一个开关所在行列的 +
总数少 2。
但仍然都满足 $\color{red}{两个开关所在行列的 + 总数为奇数。}$ (因为第二个开关改变带来的影响是偶数)
++++ ---- ++++ ++-+
+--- -> +-+- +--- -> +-+-
+--- +-+- +--- -+++
+--- +-+- +--- +-+-
(a) (b)
改变 n 个开关时
它可以视作是 多个第 2 个开关的叠加
,除了第 1 个开关之外,其余每个开关带来的影响都是偶数的,并不会改变开关所在行列 +
总数的奇偶性质。
因此本题我们只需判断哪些儿开关所在行列的 +
总数是奇数即可。
时间复杂度
$O(4 \times 4)$
优雅,实在太优雅啦!orz!
参考文献
Python 代码
res = 0
ways = []
g = []
for i in range(4):
g.append(input())
def check(x,y):
nums = 0
for i in range(4):
if g[x][i] == '+':
nums += 1
if g[i][y] == '+':
nums += 1
if g[x][y] == '+':
nums -= 1
return nums & 1
for i in range(4):
for j in range(4):
if check(i,j):
res += 1
ways.append((i,j))
print(res)
for way in ways:
print(f"{way[0] + 1} {way[1] + 1}")
算法2
暴力枚举
参照 95. 费解的开关,我也定义了一个 op
用于穷举操作方案,由于是 $4 \times 4$ 矩阵,所以存在 $2^{16} = 65536$ 种方案,对每一种方案判断是否达到最终状态,并记录最小方案。
时间复杂度
$ O(65536 \times 16 \times 4) $
Python 代码
import copy
res = 17
ways = []
g = []
for i in range(4):
g.append(list(input()))
def turn(x, y):
for i in range(4):
backup[x][i] = chr(ord(backup[x][i]) ^ 6)
backup[i][y] = chr(ord(backup[i][y]) ^ 6)
backup[x][y] = chr(ord(backup[x][y]) ^ 6)
def check(backup):
for i in range(4):
if backup[i].count('-') != 4:
return False
return True
for op in range(65536):
wait_way = []
step = 0
backup = copy.deepcopy(g)
for i in range(16):
if op >> i & 1:
a = i // 4
b = i % 4
step += 1
turn(a, b)
wait_way.append((a, b))
if check(backup):
if step < res:
ways = wait_way.copy()
res = step
print(res)
for way in ways:
print(f"{way[0] + 1} {way[1] + 1}")