AcWing 327. 玉米田 python实现
原题链接
简单
作者:
思念聚成海
,
2021-12-06 14:00:19
,
所有人可见
,
阅读 256
python好像没有取反的符号
按照y总的思路时实现的,提前预处理好合法的状态和玉米地
N = 14
M = 1 << N
mod = pow(10,8)
m,n = map(int,input().split())
g = [0]*N
# 判断相邻位置是否全为1,是否冲突
def check(x):
if (x & (x << 1)) == 0:
return True
return False
# 预处理玉米地,取反
for i in range(1,m+1):
temp = list(map(int,input().split()))
for j in range(n):
g[i] += (temp[j] ^ 1) << j
# 预处理合法状态
state = []
for i in range(1 << n):
if check(i): state.append(i)
# 预处理合法的状态转移
move = [[] for _ in range(M)]
for i in state:
for j in state:
if (i & j) == 0:
move[i].append(j)
f = [[0]*M for _ in range(N)]
f[0][0] = 1
for i in range(1,m+2):
for j in state:
if (j & g[i]) == 0:
for k in move[j]:
f[i][j] = (f[i][j] + f[i-1][k]) % mod
print(f[m+1][0])