Consider a $$$source$$$-$$$sink$$$ cut $$$(S, T)$$$. Let $$$U = S - \lbrace source \rbrace $$$ and $$$V = T - \lbrace sink \rbrace$$$. Also we'll denote the weight of an $$$u$$$-$$$v$$$ edge by $$$w(u,v)$$$(it is 0 if no such edge exists). Now the weight of the cut is

Note that

equals the number of edges whose both endpoints lie in $$$U$$$ times 2. Therefore, the last term is the score we'd get, multiplied by 2, if we were to pick $$$U$$$ as the answer. Since we want to maximize it, our goal turns into finding minimum weight $$$source$$$-$$$sink$$$ cut, which is equal to the maximum flow.

Let $$$\omega$$$ be a transfinite value, such that for integers $$$a, b, c, d,$$$ $$$a \omega + b \gt c \omega + d \Leftrightarrow a \gt c \vee (a = c \wedge b \gt d)$$$

(in other words, these numbers compare as lexicographic tuples $$$(a, b)$$$. In practice, $$$\omega$$$ can be represented with a constant large enough to dominate lesser values, but small enough not to overflow a machine integer type, e.g. $$$2^{48}$$$.)

The flow network should have:

• A vertex for each grid cell $$$(i, j)$$$, and two additional vertices $$$s$$$ and $$$t$$$, for the source and sink respectively.
• a $$$\omega$$$-capacity edge from $$$s$$$ to each $$$(i, j)$$$
• a $$$C$$$-capacity edge between each diagonally-adjacent pair of grid cells, in both directions
• an edge with capacity $$$\omega - 2\cdot A_{i, j} + (4 - deg(i, j)) \cdot C$$$ from each $$$(i, j)$$$ to $$$t$$$, where $$$deg(i, j)$$$ is the number of cells diagonally adjacent to cell $$$(i, j)$$$.

The final answer is equal to $$$\large \frac{H \cdot W \cdot \omega - maxFlow} 2$$$.

Explanation: Let a cut be a partition of vertices in the network into sets $$$S$$$ and $$$T$$$, such that $$$s \in S$$$, $$$t \in T$$$. Let the cost of the cut be the sum of the capacity of edges going from vertices $$$u \in S$$$ to $$$v \in T$$$. By the max-flow-min-cut theorem, the minimum cost of a cut is equal to the maximum flow.

We wish to build the network in such a way such that $$$(i, j) \in S$$$ represents marking an X in that cell.

First, let's ignore the $$$(4 - deg(i, j)) \cdot C$$$ terms in the sink-edges. If $$$(i, j) \in S$$$, that means that if we followed the $$$C$$$-capacity edges until we reach a cell that's $$$\in T$$$, we cut the edge just before it. (Let's ignore the case where we reach the edge of the grid for now.) Also, we cut the edge from $$$(i, j)$$$ to $$$t$$$, Thus the cost of the cut is $$$2\cdot C$$$ for each line drawn, plus $$$\omega - 2 \cdot A_{i, j}$$$ for each chosen cell. If $$$(i, j) \in T$$$ instead, we just cut the $$$\omega$$$-capacity source-edge; any edges that may connect it to $$$s$$$ has already been cut.

Now we go back to the case where a drawn line reaches the edge of the grid. To model that cost correctly, we want to cut a $$$C$$$-capacity edge. Where should it go? Well, we can imagine it going to a fake node that's always $$$\in T$$$. But if we want to do that, we might as well connect it to $$$t$$$ directly. But since there's already an edge going there, we can simply add the capacities together, which is where the $$$(4 - deg(i, j)) \cdot C$$$ term comes from: there are $$$4 - deg(i, j)$$$ "missing" edges, each of cost $$$C$$$, that has been merged into the sink-edge.

If $$$x$$$ is the total number of lines drawn, we can thus see the total cost of the cut is $$$H \cdot W \cdot \omega - 2 \cdot (\sum_{(i, j) \in S} [A_{i, j}] - x \cdot C)$$$. Since $$$\sum_{(i, j) \in S} [A_{i, j}] - x \cdot C$$$ is our desired score, we can thus verify that the procedure is correct.