For simplicity, we regard + and - collectively as empty cells ..

Condition that the resulting grid must satisfy

The form of the operation implies that the resulting grid necessarily satisfy the following two conditions:

• For two horizontally adjacent . cells, they both become . or both become #.
• For two vertically adjacent . cells, if the lower one becomes ., then the upper one becomes ..

Conversely, any grid satisfying these two conditions can be realized. Specifically, it suffices to repeat choosing . cells that eventually becomes # cells as long as there are any.

---

Reducing to minimum cut

First, we briefly explain what an \(s\)-\(t\) cut is.

A partition of the vertex set into a set \(S\) containing \(s\) and a set \(T\) containing \(t\) is called an \(s\)-\(t\) cut. A directed graph \(u\to v\) is said to be cut when \(u\in S,\ v\in T\), and the sum of the capacities of such edges is called the capacity of the cut. A minimum cut problem asks to find a partition that minimizes this capacity of a cut. It is known that this coincides with the value of the maximum flow from \(s\) to \(t\), by the max-flow min-cut problem.

---

Define a vertex corresponding to each . cell, as well as a source vertex \(s\) and a sink vertex \(t\). For each vertex \(v\) corresponding to a . cell:

• Interpret \(v\in S\) as keeping that cell to ..

• Interpret \(v\in T\) as turning that cell into #.

Here, consider adding edges so that the capacity of a minimum cut corresponds to the sum of “loss of score.”

First, let us consider the condition that the resulting grid must satisfy. All the conditions in the beginning can be represented as a combination of the form

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

To enforce this, add an edge \(u \to v\) of capacity \(\mathrm{INF}\) to (essentially) prevent this edge from being cut.

Next, we will represent the scores yielded by + and -. (Since a gain of score cannot be simply represented) we assume that we unconditionally receive a score as many as the number of + cells, and add the following edges:

• Turning a + cell into # imposes a loss of score of \(1\). This is represented by adding an edge \(s\to v\) of capacity \(1\).
• Keeping a - cell to . imposes a loss of score of \(1\). This is represented by adding an edge \(v\to t\) of capacity \(1\).

This graph construction encodes all the conditions. Denoting by \(C\) the minimum cut capacity, the maximum possible score precisely equals “the number of + cells \(\ -C\).”

---

Hence, it is sufficient to solve a max-flow problem on a graph with \(O(HW)\) vertices and \(O(HW)\) edges. Using Dinic’s algorithm, the time complexity is \(O(V^2E)\), which is \(O((HW)^3)\) in our graph.

---

Sample code

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))