AcWing 95. 费解的开关
原题链接
中等
作者:
冉俊泽
,
2024-04-19 15:42:32
,
所有人可见
,
阅读 1
python 递归法
import copy
dx=[-1,1,0,0,0]
dy=[0,0,0,-1,1]
def turn(x,y,g):
for i in range(5):
a=x+dx[i]
b=y+dy[i]
if 0<=a<5 and 0<=b<5:
g[a][b]='0' if g[a][b]=='1' else '1'
def dfs(u):
global res
global step
global g
backup=copy.deepcopy(g)
if u==5:
step=0
for i in range(5):
if state[i]==1:
step=step+1
turn(0,i,g)
for i in range(4):
for j in range(5):
if g[i][j]=='0':
step=step+1
turn(i+1,j,g)
dark=any(g[4][i]=='0' for i in range(5))
if not dark:
res=min(res,step)
g=copy.deepcopy(backup)
return
state[u]=1
dfs(u+1)
state[u]=0
dfs(u+1)
n=int(input())
for i in range(n):
res=10
step=0
g=[list(input()) for _ in range(5)]
if i<n-1:
input()
state=[0]*(6)
dfs(0)
if res>6:
print(-1)
else:
print(res)