AcWing 292. 炮兵阵地-python
原题链接
中等
作者:
viclao
,
2023-10-31 20:33:06
,
所有人可见
,
阅读 49
n,m = map(int,input().split())
# 首先考虑一行的状态是否合法,1不能建立在H上,要求两个一最少要间隔2(x - y > 2)
# 把PHPP改成1011,要求s&row[i] == s
grid = [] # 让下标从1开始
for _ in range(n):
x = ''.join('1' if x=='P' else '0' for x in input())
grid.append(int(x,2))
grid.append(0)
grid.append(0)
def check(s):
for i in range(1 << m):
if (s >> i & 1) and ((s >> i + 1 & 1) or (s >> i + 2 & 1)):
return False
return True
def bit_count(s):
res = 0
while s:
s &= (s - 1)
res += 1
return res
# 不过滤状态这题会tle,不滚动数组会mle
states = []
cnt = []
for i in range(1 << m):
if check(i):
states.append(i)
cnt.append(bit_count(i))
# 考虑定义状态,当前行与前两行都有关系,考虑三维
f = [[[0]*(1<<m) for _ in range(1<<m)] for _ in range(2)]
# 考虑状态转移
for i in range(1,n + 3):
for a,s1 in enumerate(states): # 枚举当前行
if (s1&grid[i - 1]) == s1:
for b,s2 in enumerate(states): # 枚举上一行
if (s2&grid[i - 2]) == s2 and (s1&s2) == 0:
for c,s3 in enumerate(states):# 枚举上上行
if ((s1&s2) |(s2&s3) | (s1&s3)) == 0:
f[i&1][a][b] = max(cnt[a] + f[i - 1&1][b][c],f[i&1][a][b])
print(f[n+2&1][0][0])