# 誤解法: 各行の最終列の良いマスの条件チェック漏れ import sys def solve(N, M, S): fire = [[S[i][j] == '#' for j in range(M)] for i in range(N)] def fire_cnt(i, j): c = 0 for di in (-1, 0, 1): for dj in (-1, 0, 1): if di == 0 and dj == 0: continue a, b = i + di, j + dj if 0 <= a < N and 0 <= b < M and fire[a][b]: c += 1 return c # 良いマスになり得る候補 = 空きマス かつ 火の隣接が 2 個以上 cand = [[(not fire[i][j]) and fire_cnt(i, j) >= 2 for j in range(M)] for i in range(N)] # 各マスの状態(植えない空きマスは「植える」に置き換えても損しない) # 0: 植物なし・要求なし(火 or 条件達成済みの良いマス) # 1: 植物あり # 2: 良いマス(あと 1 個植物が必要) # 3: 良いマス(あと 2 個植物が必要) # プロファイル: 直近 M+1 マス(行優先)の状態。 # state[k] = k マス前に決めたマスの状態 (k=1..M+1) を 2bit ずつ詰める。 W = M + 1 mask_all = (1 << (2 * W)) - 1 def get(st, k): # k マス前 (1-indexed) return (st >> (2 * (k - 1))) & 3 dp = {0: 0} # 盤面の外は状態 0(植物なし・要求なし)扱い for i in range(N): for j in range(M): # 既に決まっている隣接マス: 左 (k=1), 左上 (k=M+1), 上 (k=M), 右上 (k=M-1) nbrs = [] if j > 0: nbrs.append(1) if i > 0: nbrs.append(M) if j > 0: nbrs.append(M + 1) if j < M - 1: nbrs.append(M - 1) if fire[i][j]: opts = (0,) elif cand[i][j]: opts = (1, 3) else: opts = (1,) ndp = {} for st, val in dp.items(): for o in opts: s = st cur = o ok = True if o == 1: # 植えたので、隣接の良いマスの要求を減らす for k in nbrs: v = get(s, k) if v >= 2: nv = 0 if v == 2 else 2 s ^= (v ^ nv) << (2 * (k - 1)) elif o == 3: need = 2 for k in nbrs: if get(s, k) == 1: need -= 1 cur = (0, 2, 3)[max(need, 0)] # M+1 マス前 (= 左上) はこれで隣接 8 マスが全部確定 → 検証して捨てる if i > 0 and j > 0: if get(s, M + 1) >= 2: ok = False if not ok: continue ns = ((s << 2) | cur) & mask_all nv = val + (1 if o == 3 else 0) if ndp.get(ns, -1) < nv: ndp[ns] = nv dp = ndp # 行末: 1 つ上の行の最後のマス (i-1, M-1) は今の行の (i, M-1) で # 隣接が全確定しているので、ここで検証する(k = M+1 にいる) # 最終行の良いマスは下側が存在しないので、要求が残っていないかを確認 best = 0 for st, v in dp.items(): if all(get(st, k) < 2 for k in range(1, M + 1)): best = max(best, v) return best def main(): data = sys.stdin.read().split() N, M = int(data[0]), int(data[1]) S = data[2:2 + N] print(solve(N, M, S)) if __name__ == "__main__": main()