簡単のため + - をまとめて空マス . として扱います。

操作後のグリッドが満たすべき条件

操作から、残ったグリッドについて以下の \(2\) つの条件が必要であることはわかります。

• 左右に隣り合う \(2\) つの . マスは、ともに . かともに #
• 上下に隣り合う \(2\) つの . マスは、下が . ならば上も .

逆にこの \(2\) つの条件を満たすグリッドは実現できます。具体的には「最終的に # になる . マスが残っているならば選んで操作する」を繰り返せばよいです。

---

最小カットへの帰着

まず \(s\)-\(t\) カットについて簡単に説明します。

頂点集合を、\(s\) を含む集合 \(S\) と \(t\) を含む集合 \(T\) に分割することを \(s\)-\(t\) カットと呼びます。有向辺 \(u\to v\) は、\(u\in S,\ v\in T\) のときにカットされ、そのような辺の容量の総和をカット容量と呼びます。最小カットとは、このカット容量を最小にする分割を求める問題です。そして、これは「最大フロー最小カット定理」によって、\(s\) から \(t\) への最大フローの値と一致することが知られています。

---

各 . マスに対応する頂点を \(1\) つずつ作り、さらに始点 \(s\) と終点 \(t\) を用意します。各 . マスに対応する頂点 \(v\) について、

• \(v\in S\) なら、そのマスを . のまま残す

• \(v\in T\) なら、そのマスを # にする

と対応させます。ここで、最小カットの容量が「失った得点の総和」になるように辺を張ることを考えます。

まず、操作後のグリッドが満たすべき条件を表します。先ほどの条件はすべて

• \(u\in S\Rightarrow v\in S\)

という形の組み合わせで表せます。これを強制するため、\(u \to v\) に容量 \(\mathrm{INF}\) の辺を張り、（実質的に）この辺をカットできないようにします。

次に、+, - による得点を表します。（得点を得るは簡単には表現できないため）あらかじめ + の個数だけ得点を持っていると考えると、以下のような辺を張ればよいです。

• + のマスを # にすると \(1\) 点失う。これは \(s\to v\) に容量 \(1\) の辺を張って表現する
• - のマスを . のまま残すと \(1\) 点失う。これは \(v\to t\) に容量 \(1\) の辺を張って表現する

このようにグラフを構築すればすべての条件が表現されています。最小カット容量を \(C\) とすると、得られる最大得点は「 + の個数\(\ -C\) 」にちょうど対応します。

---

よって、頂点数が \(O(HW)\)、辺数が \(O(HW)\) のグラフに対する maxflow を求めればよいです。例えば Dinic 法を用いると、計算量は \(O(V^2E)\) であるため、今回のグラフでは \(O((HW)^3)\) となります。

---

実装例

from atcoder.maxflow import MFGraph

h, w = map(int, input().split())
a = [input() for _ in range(h)]
n = h * w + 2
s, t = n - 2, n - 1
g = MFGraph(n)
p = 0
inf = h * w + 1

for i in range(h):
    for j in range(w):
        if a[i][j] == "#": continue
        v = i * w + j
        if a[i][j] == "+":
            g.add_edge(s, v, 1)
            p += 1
        else:
            g.add_edge(v, t, 1)
        
        if j + 1 < w and a[i][j + 1] != "#":
            g.add_edge(v, v + 1, inf)
            g.add_edge(v + 1, v, inf)
        if i + 1 < h and a[i + 1][j] != "#":
            g.add_edge(v + w, v, inf)

print(p - g.flow(s, t))